Bug 19221 - Counterintuitive behaviour in matrix multiplication
Summary: Counterintuitive behaviour in matrix multiplication
Alias: None
Product: pycairo
Classification: Unclassified
Component: general (show other bugs)
Version: unspecified
Hardware: Other All
: medium normal
Assignee: Steve Chaplin
QA Contact:
Depends on:
Reported: 2008-12-21 10:09 UTC by Pietro Battiston
Modified: 2009-06-13 04:44 UTC (History)
1 user (show)

See Also:
i915 platform:
i915 features:

Patch to reverse order of arguments in "*" operator for matrices. (371 bytes, patch)
2008-12-21 10:09 UTC, Pietro Battiston
Details | Splinter Review
Patch to reverse order of arguments in "*" operator for matrices. (273 bytes, patch)
2008-12-21 12:38 UTC, Pietro Battiston
Details | Splinter Review

Description Pietro Battiston 2008-12-21 10:09:34 UTC
Created attachment 21362 [details] [review]
Patch to reverse order of arguments in "*" operator for matrices.

Cairo has an object that is called "matrix", but if A and B are "matrix"es, then

cairo_matrix_multiply (A, B)

is what, in the column vector notation, is written as B*A.

While I do understand (or, better, was convinced in IRC :-) that Cairo chose row vector notation for good reasons (in particular, to follow more the concept of transformation composition than of matrix multiplication, so that cairo_matrix_multiply(A,B) returns the transformation that first applies A, then B), this becomes totally misleading when in python we write

matrix = matrixA * matrixB

See, for example:

In [21]: cairo.Matrix(1,0,0,1,1,1)*cairo.Matrix(2,0,0,2,0,0)
Out[21]: cairo.Matrix(2, 0, 0, 2, 2, 2)

and as a counterexample:

In [17]: scipy.matrix([[1,0,1],[0,1,1],[0,0,1]]) * scipy.matrix([[2,0,0],[0,2,0],[0,0,1]])
matrix([[2, 0, 1],
        [0, 2, 1],
        [0, 0, 1]])

When one uses a function (cairo_matrix_multiply), it's his job to check documentation and behave consequently, OK. But when one uses the operator "*" over two objects called "matrix", he just expects this behaves as the matrices multiplication, which is:

lambda A, B : cairo_matrix_multiply (B, A)

I'm attaching a patch for file /pycairo/cairo/pycairo-matrix.c ; I already tested it and it does the job.
Comment 1 Pietro Battiston 2008-12-21 10:15:31 UTC
No, excuse me, part of my arguments are misleading. This is not a point of vector column/row notation, the point is just that

cairo_matrix_multiply (A, B)

returns B*A, given any matricial notation you desire.

So I should have written "while I do understand that this function reverses its arguments for some good reason, which is related to the concept of transformation, when we talk about an operator on matrices..." and so on.

Anyway, the patch is OK.
Comment 2 Pietro Battiston 2008-12-21 12:38:59 UTC
Created attachment 21366 [details] [review]
Patch to reverse order of arguments in "*" operator for matrices.
Comment 3 Steve Chaplin 2008-12-27 00:55:54 UTC
The first patch looks OK, the second one passes pycairo data into cairo which is no good - looks like the patches are in the wrong order.

It looks name 'matrix' is a bad name - its not a matrix, its a vector, or a matrix representation.

I created the new method cairo.Matrix.multiply() to call cairo_matrix_multiply(), and changed matrixA * matrixB to call cairo_matrix_multiply (B, A) - so both the cairo way and the 'proper' way are supported.
Comment 4 Carl Worth 2009-04-07 11:51:16 UTC
Sorry to open up an old issue, but I just ran across this now, and felt compelled to address some misinformation, and point out what I see as a possible bug in the approach of the python bindings.

(In reply to comment #1)
> No, excuse me, part of my arguments are misleading. This is not a point of
> vector column/row notation, the point is just that
> cairo_matrix_multiply (A, B)
> returns B*A, given any matricial notation you desire.

That's not true.

cairo_matrix_multiply (A, B) does give you the result A*B for a matrix that assumes row-vector notation. It's definitely not reversed in cairo itself.

A cairo_matrix_t uses 3x2 storage:

typedef struct _cairo_matrix {
    double xx; double yx;
    double xy; double yy;
    double x0; double y0;
} cairo_matrix_t;

to implicitly represent a 3x3 matrix:

[xx yx 0]
[xy yy 0]
[x0 y0 1]

And cairo_matrix_multiply (A, B) gives the product of A*B in that order. Specifically, A*B => R is defined as:

[A.xx A.yx 0] [B.xx B.yx 0]  [A.xx*B.xx+A.yx*B.xy      A.xx*B.yx+A.yx*B.yy 0]
[A.xy A.yy 0]*[B.xy B.yy 0]=>[A.xy*B.xx+A.yy*B.xy      A.xy*B.yx+A.yy*B.yy 0]
[A.x0 A.y0 1] [B.x0 B.y0 1]  [A.x0*B.xx+A.y0*B.xy+B.x0 A.x0*B.yx*A.y0*B.yy+B.y0 1]

And you can verify the same operation is implemented in cairo_matrix_multiply as seen here:

    r.xx = a->xx * b->xx + a->yx * b->xy;
    r.yx = a->xx * b->yx + a->yx * b->yy;

    r.xy = a->xy * b->xx + a->yy * b->xy;
    r.yy = a->xy * b->yx + a->yy * b->yy;

    r.x0 = a->x0 * b->xx + a->y0 * b->xy + b->x0;
    r.y0 = a->x0 * b->yx + a->y0 * b->yy + b->y0;

So if I made any mistake in the derivation above, then I made the same mistake in the cairo implementation. :-)

But more than that claim about cairo's implementation, I'm more concerned that the python binding might be intentionally deviating from cairo's implementation. I'm not sure what the storage of the python objects is, but I'm extremely nervous to see this comment in the bug traffic:

    "[I just] changed matrixA * matrixB to call cairo_matrix_multiply (B, A)"

Even if cairo_matrix_multiply *did* have a bug, it would be very wrong for the bindings to try to correct that. The bindings must be faithful to cairo, or else we run into difficulties porting code from one binding to another, as well as create conceptual difficulties in people's minds as they try to move from one binding to another.

So I'm very nervous about the above attitude, and I would love to see someone verify that the pycairo matrix objects behave like the cairo objects. And if they aren't doing that curently, please fix them.


Comment 5 Pietro Battiston 2009-04-07 14:33:50 UTC
I have to think about the merit of the issue (the matrices notation), I'll come back tomorrow.

On one point only I want to be clear: the bindings deviating from the C libraries are not really an issue, since there is a big difference between having a library function with "multiply" in the name and having an "*" operator.

In other words, if comment #1 is really wrong, I will recognize my fault, but the bug description is still here, and I will still think that the fix was good: C doesn't even know of an "*" operator, and python must introduce it coherently with other "*" operators, for instance in other libraries which manage matrices. There are two ways you could point I'm wrong:
- show that there are python libraries that follow your convention, so it's not true that mine is the de facto standard (I don't pretend I'm a programming guru, but I surely would be suprised[0])
- drop the name "matrix" and call it in some other way (like "matrix_in_row_vector_notation", or better still "transformation")

[0] notice I don't talk about implementations - of which we already talked in chat, maybe with you, and I'm ignorant - I talk about exposed APIs (in python I know only scipy, but every other mathematic software I used in my life followed the same criterion)
Comment 6 Pietro Battiston 2009-04-11 02:01:34 UTC
Sorry for taking longer than one night...

I now understand the implementation, and I understand that - while changing to row-column to row-vector assumption should have in principle nothing to do with the rule used for multiplication - the point I was missing is that using row-vector assumption obviously also means that the coefficient representing the translations will have to be stored in the bottom row instead than in the rightmost column (notice I couldn't find anywhere else the info you provided, so I'd copypaste it in the matrix_multiply documentation, or at least in http://cairographics.org/matrix_transform/).

In other words, what was misleading in my first posting of the bug was that 
is not

To this point, I certainly admit that from a just mathematical point of view your way of reasoning and mine are equally valid. That said...

I wouldn't really worry about pycairo deviating from C cairo; as I already said, there is no "*" to compare with. However:
- the real issue I didn't think to is that pycairo deviates from other bindings (I just tested in ruby)
- when I first posted the bug, I was worried a "fix" could break existing code, and I was answered in chat "well, let's hope that if a programmer finds a bug in a free software library's API, he will file it and not work around it!"... it made sens, but now we see it is not really a bug, but more a question of tastes, this may indeed be an issue.

So in the end I think the best approach is to rollback the "fix" - I and probably other people would probably prefer to change all the others bindings, but I'm afraid it's not worth the effort.
Comment 7 Steve Chaplin 2009-06-13 04:44:47 UTC
The original bugfix was a mistake. I've undone the change so that
matrix3 = matrix1 * matrix2
is the same as
matrix3 = matrix1.multiply(matrix2)

Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.