4 ms·

Abstractly, a vector is neither a row nor a column. An n-dimensional vector is an ordered collection of n coordinates. An m by n matrix is an m-dimensional vect

Abstractly, a vector is neither a row nor a column. An n-dimensional vector is an ordered collection of n coordinates. An m by n matrix is an m-dimensional vector of n-dimensional vectors. But when you define a matrix in most programming languages you can only really write it like this: mat = [ [1,2,3], [4,5,6], [7,8,9] ] Note that the inner vectors are laid out as rows, and the outer vector (the matrix) is laid out as a column. Some languages have fancy syntax that omits the need for braces. But for those that don't, this is clearly an array of 3 arrays of 3 ints. It's only intuitive to think of this as an array of rows given how it's laid out visually. I also think in that context it would make more sense to index it as mat[row][col], or in other words row major indexing. Because of that, it also makes sense to store the mat row-major, that is, laid out in memory as [1,2,3,4,5,6,7,8,9] so that mat[row][col] becomes mem[row*3 + col]. This is also how C does it. I think it was a mistake for OpenGL to break with that C convention given how close the relationship between C and OpenGL is. Mathematicians be damned.

IshKebab 4y ago
Yeah having used Matlab extensively it's pretty clear that maths just got some things wrong. 1-based indexing is wrong. Matrix index ordering is wrong (try dealing with images in Matlab if you don't believe me). Mathematicians generally don't care because equations are basically pseudocode and they can make up new syntax and hand-wave edge cases away whenever they want.
rocqua 4y ago
Very true, and I think this is generally why C 'does it right'. But there are caveats. Firstly, almost no-one actually creates their matrices as literals. Instead they are build dynamically an usually incrementally. Nevertheless, people still think back to these very basic examples when trying to understand things, so this probably should be standard. Secondly, these decisions matter a lot for matrix vector multiplication. The 'C' way is very efficient for computing Ax which presumes vector x to be a Column vector. When you want to compute xA instead which presumes vector x to be a row vector, you want column-major ordering for efficiency. The same works for matrix-matrix multiplication AB where you want A to be row-major and B to be column-major. To sum up. Because of our writing direction, and the natural way to write 2-d arrays, it makes sense to have row-major ordering. That immediately means it also makes sense to use column vectors, generally speaking. There are also exceptions if you happen to know if a matrix will often be at the 'left' or 'right' side of a multiplication. Some more interesting notes that are less relevant: In C the matrix you defined has an incompatible type with how most matrices are stored (most people in C store rows contiguously, then define a matrix as an array of pointers to rows). int mat[3][3]; vs int *mat[3] These are meaningfully different. In the first case getting element `mat[1][1]` is just 'base-pointer + 4'. Whereas in the second case, getting element `mat[1][1]` is 'read pointer at base-pointer + 1 and add 1 to the added pointer`. Another common ways to use matrices is element-wise, where you refer to x[i][j]. Mathematicians expect i to be the row and j to be the column. Which matches C. Whilst Fortran does it the other way around.
- bruce343434 4y ago
  vs int (*mat)[3] = calloc(3, sizeof(int[3])); which is a pointer to (or array of) arrays of 3 ints. Laid out flat, and you still get the `mat[i][j]` notation.
  - rocqua 4y ago
    That is indeed almost the same as int mat[3][3] The biggest reason people use the separate array of pointers is for very quick row swaps. Often comes up in matrix operations when trying to solve systems or put matrices in triangular forms.
- owlbite 4y ago
  > The 'C' way is very efficient for computing Ax which presumes vector x to be a Column vector. When you want to compute xA instead which presumes vector x to be a row vector, you want column-major ordering for efficiency. You have this the wrong way around. The C row-major ordering is better for A^Tx, the Fortran column-major format is better for Ax. If you do Ax in row-major, you end up multiplying a row of A by x as your simd vector op. This then leaves you needing to horizontally reduce the result, which you avoid by using a column-major layout that instead accumulates multiple different results.
  - bruce343434 4y ago
    wait, so a row major stored matrix should be multiplied by extracting the columns first? Or what? Is there some sort of animation that illustrates Ax and xA for both row major storage and column major storage?
    - kergonath 4y ago
      > wait, so a row major stored matrix should be multiplied by extracting the columns first? Or what? No, the other way around. In row-major storage, all the elements of the same row are contiguous, so it is faster to process the array row by row. > Is there some sort of animation that illustrates Ax and xA for both row major storage and column major storage? The explanations here are decent enough. All you need is the figure at the top, really: https://en.m.wikipedia.org/wiki/Row-_and_column-major_order https://en.m.wikipedia.org/wiki/Row-_and_column-major_order .
contravariant 4y ago
Hey! Don't just blame the mathematicians, if it were up to them you could notate column vectors as actual columns. Mathematicians use row-major indexing just like any sensible person.
- joppy 4y ago
  Mathematicians index the ith row and jth column of their n x m matrix as (i, j), which is nothing to do with row-major or column-major order. Those orderings are how a two-dimensional index is flattened to a one-dimensional index. Row-major makes it so that each row is stored one after the other: (i, j) goes to mi + j. Column-major uses i + nj instead.
  - contravariant 4y ago
    That's as may be but M[i][j] and Mij still refer to the same element.
    - bee_rider 4y ago
      This doesn't tell us anything about memory layout though. If a mathematician actually has to write out their matrices, they do it on a piece of paper. Because it is a 2D medium, the each element can have two "neighbors" on in the next row, and one in the next column. If they do their math on a computer, they have the same problem as the rest of us -- but, they probably just use BLAS, which is typically column major. Although, I think some of the more modern BLAS spinoffs accept a layout option: https://www.intel.com/content/www/us/en/develop/documentation/onemkl-developer-reference-c/top/blas-and-sparse-blas-routines/blas-routines/blas-level-3-routines/cblas-gemm.html https://www.intel.com/content/www/us/en/develop/documentatio...
benreesman 4y ago
I think that whatever combination of tools/docs/compilers that makes row vs. column major notationally equivalent, amenable to introspection, and equally amenable to optimization will win big. I’ve written godawful python extensions to feed TF or PyTorch mmapped regions to the pipeline in an efficient way. This is currently the way of things. But half the trouble in model architecture engineering is keeping the ranks straight and having tools to debug when you messed up. Einstein struggled with tensor math, read his letters. But he didn’t have modern computers or autodiff either. For that era, thinking in higher dimensions was a job for a genius. I harbor a vague suspicion that some people get paid more because it’s needlessly hard.
- pizza 4y ago
  einops, einsum, pytrees, named tensors, and xla/jit/tensor compilation (jax/tvm/taco) will hopefully improve things
dannymi 4y ago
>Some languages have fancy syntax that omits the need for braces. But for those that don't, this is clearly an array of 3 arrays of 3 ints. >It's only intuitive to think of this as an array of rows given how it's laid out visually. That's often the least important thing when designing a fast library. It's much better to optimize for common operations in your problem to be fast and thus choose the storage layout of a individual matrix instance accordingly (row-major, column-major, triangular, diagonal, block diagonal, band) so your data cache doesn't get tripped up regularily. The actual API for creating new matrices can still be standardized and always the same. You can have the standardized API accept four column vectors for construction just as well. Just document it as such. If you want, you can also represent the different kinds of vectors as different types, so you don't get identification problems that shouldn't exist. Also, lists of vectors are just that and there's no reason to represent both "list" and "vector" as "array". There are reasons to make the API for "vector" richer--especially since that's why the term "vector" was defined in the first place. But for tiny 4x4 matrices, who cares about caching. But 4x4 are a minority use of matrices. Try 4096x4096. As for OpenGL, they chose to keep the internal storage of matrices the same as it was on IRIS GL. That's a good decision for OpenGL and orthogonal to the question of how column vectors of that matrix can be accessed via an API and to the question of how row vectors of that matrix can be accessed via an API and to the question of how matrices can be created via an API. From a mathematics standpoint, a matrix represents a linear map (a map is a function that takes a vector in space V to a vector in space W). It makes sense to be able to use matrix and linear map interchangeably as a user (i.e. use them just like you would call functions).
- bruce343434 4y ago
  > Try 4096x4096 Where should I, if we keep the context of OpenGL? Apart from that, I consider this an implementation issue. My post was mostly about keeping a consistent "front end" semantics. However the compiler or library transforms the data does not pertain to it. To be fair, I mentioned memory layout. If I had left that out, would we agree with eachother?
  - dannymi 4y ago
    (Column|Row) Vectors and matrices are abstractions, and having abstractions that are always the same API in all of programming (not just OpenGL) would be nice. Of course making them again and again different and dumb is easier. So we got a lot of programs with weird arrays with no information on what matrix is what style. And thus readers get confused because half the information is missing in the source code! That makes things needlessly obtuse. But let's say one would try to make the API for column vectors (resp row vectors resp matrices) always the same (OpenGL or not), then it's important to look at bigger matrices. Otherwise you wouldn't care about storage layout at all and that's gonna come back to bite you in the ass (several orders of magnitude slower than possible). >But when you define a matrix in most programming languages you can only really write it like this: mat = [ [1,2,3], [4,5,6], [7,8,9] ] I wouldn't repurpose arrays like that.
VyseofArcadia 4y ago
> Abstractly, a vector is neither a row nor a column. An n-dimensional vector is an ordered collection of n coordinates. An m by n matrix is an m-dimensional vector of n-dimensional vectors. Oh we can get more abstract than that. A vector is an element of a vector space, or, if you'd like, an F-module where F is a field. A matrix is a homomorphism between vector spaces.
- panda-giddiness 4y ago
  To give an explicit example that breaks the column-vector mold: the set of 2x2 matrices with real entries forms a vector space, where each vector is a 2x2 matrix.
  - VyseofArcadia 4y ago
    Let's get even weirder and leave finite dimensions behind. The set of sequences of complex numbers z_n such that the infinite sum from i = 1 to infinity of |z_i|^2 converges.

IshKebab 4y ago

Yeah having used Matlab extensively it's pretty clear that maths just got some things wrong. 1-based indexing is wrong. Matrix index ordering is wrong (try dealing with images in Matlab if you don't believe me). Mathematicians generally don't care because equations are basically pseudocode and they can make up new syntax and hand-wave edge cases away whenever they want.

rocqua 4y ago

Very true, and I think this is generally why C 'does it right'. But there are caveats. Firstly, almost no-one actually creates their matrices as literals. Instead they are build dynamically an usually incrementally. Nevertheless, people still think back to these very basic examples when trying to understand things, so this probably should be standard. Secondly, these decisions matter a lot for matrix vector multiplication. The 'C' way is very efficient for computing Ax which presumes vector x to be a Column vector. When you want to compute xA instead which presumes vector x to be a row vector, you want column-major ordering for efficiency. The same works for matrix-matrix multiplication AB where you want A to be row-major and B to be column-major. To sum up. Because of our writing direction, and the natural way to write 2-d arrays, it makes sense to have row-major ordering. That immediately means it also makes sense to use column vectors, generally speaking. There are also exceptions if you happen to know if a matrix will often be at the 'left' or 'right' side of a multiplication. Some more interesting notes that are less relevant: In C the matrix you defined has an incompatible type with how most matrices are stored (most people in C store rows contiguously, then define a matrix as an array of pointers to rows). int mat[3][3]; vs int *mat[3] These are meaningfully different. In the first case getting element `mat[1][1]` is just 'base-pointer + 4'. Whereas in the second case, getting element `mat[1][1]` is 'read pointer at base-pointer + 1 and add 1 to the added pointer`. Another common ways to use matrices is element-wise, where you refer to x[i][j]. Mathematicians expect i to be the row and j to be the column. Which matches C. Whilst Fortran does it the other way around.

bruce343434 4y ago
vs int (*mat)[3] = calloc(3, sizeof(int[3])); which is a pointer to (or array of) arrays of 3 ints. Laid out flat, and you still get the `mat[i][j]` notation.
- rocqua 4y ago
  That is indeed almost the same as int mat[3][3] The biggest reason people use the separate array of pointers is for very quick row swaps. Often comes up in matrix operations when trying to solve systems or put matrices in triangular forms.
owlbite 4y ago
> The 'C' way is very efficient for computing Ax which presumes vector x to be a Column vector. When you want to compute xA instead which presumes vector x to be a row vector, you want column-major ordering for efficiency. You have this the wrong way around. The C row-major ordering is better for A^Tx, the Fortran column-major format is better for Ax. If you do Ax in row-major, you end up multiplying a row of A by x as your simd vector op. This then leaves you needing to horizontally reduce the result, which you avoid by using a column-major layout that instead accumulates multiple different results.
- bruce343434 4y ago
  wait, so a row major stored matrix should be multiplied by extracting the columns first? Or what? Is there some sort of animation that illustrates Ax and xA for both row major storage and column major storage?
  - kergonath 4y ago
    > wait, so a row major stored matrix should be multiplied by extracting the columns first? Or what? No, the other way around. In row-major storage, all the elements of the same row are contiguous, so it is faster to process the array row by row. > Is there some sort of animation that illustrates Ax and xA for both row major storage and column major storage? The explanations here are decent enough. All you need is the figure at the top, really: https://en.m.wikipedia.org/wiki/Row-_and_column-major_order https://en.m.wikipedia.org/wiki/Row-_and_column-major_order .

contravariant 4y ago

Hey! Don't just blame the mathematicians, if it were up to them you could notate column vectors as actual columns. Mathematicians use row-major indexing just like any sensible person.

joppy 4y ago
Mathematicians index the ith row and jth column of their n x m matrix as (i, j), which is nothing to do with row-major or column-major order. Those orderings are how a two-dimensional index is flattened to a one-dimensional index. Row-major makes it so that each row is stored one after the other: (i, j) goes to mi + j. Column-major uses i + nj instead.
- contravariant 4y ago
  That's as may be but M[i][j] and Mij still refer to the same element.
  - bee_rider 4y ago
    This doesn't tell us anything about memory layout though. If a mathematician actually has to write out their matrices, they do it on a piece of paper. Because it is a 2D medium, the each element can have two "neighbors" on in the next row, and one in the next column. If they do their math on a computer, they have the same problem as the rest of us -- but, they probably just use BLAS, which is typically column major. Although, I think some of the more modern BLAS spinoffs accept a layout option: https://www.intel.com/content/www/us/en/develop/documentation/onemkl-developer-reference-c/top/blas-and-sparse-blas-routines/blas-routines/blas-level-3-routines/cblas-gemm.html https://www.intel.com/content/www/us/en/develop/documentatio...

benreesman 4y ago

I think that whatever combination of tools/docs/compilers that makes row vs. column major notationally equivalent, amenable to introspection, and equally amenable to optimization will win big. I’ve written godawful python extensions to feed TF or PyTorch mmapped regions to the pipeline in an efficient way. This is currently the way of things. But half the trouble in model architecture engineering is keeping the ranks straight and having tools to debug when you messed up. Einstein struggled with tensor math, read his letters. But he didn’t have modern computers or autodiff either. For that era, thinking in higher dimensions was a job for a genius. I harbor a vague suspicion that some people get paid more because it’s needlessly hard.

pizza 4y ago
einops, einsum, pytrees, named tensors, and xla/jit/tensor compilation (jax/tvm/taco) will hopefully improve things

dannymi 4y ago

>Some languages have fancy syntax that omits the need for braces. But for those that don't, this is clearly an array of 3 arrays of 3 ints. >It's only intuitive to think of this as an array of rows given how it's laid out visually. That's often the least important thing when designing a fast library. It's much better to optimize for common operations in your problem to be fast and thus choose the storage layout of a individual matrix instance accordingly (row-major, column-major, triangular, diagonal, block diagonal, band) so your data cache doesn't get tripped up regularily. The actual API for creating new matrices can still be standardized and always the same. You can have the standardized API accept four column vectors for construction just as well. Just document it as such. If you want, you can also represent the different kinds of vectors as different types, so you don't get identification problems that shouldn't exist. Also, lists of vectors are just that and there's no reason to represent both "list" and "vector" as "array". There are reasons to make the API for "vector" richer--especially since that's why the term "vector" was defined in the first place. But for tiny 4x4 matrices, who cares about caching. But 4x4 are a minority use of matrices. Try 4096x4096. As for OpenGL, they chose to keep the internal storage of matrices the same as it was on IRIS GL. That's a good decision for OpenGL and orthogonal to the question of how column vectors of that matrix can be accessed via an API and to the question of how row vectors of that matrix can be accessed via an API and to the question of how matrices can be created via an API. From a mathematics standpoint, a matrix represents a linear map (a map is a function that takes a vector in space V to a vector in space W). It makes sense to be able to use matrix and linear map interchangeably as a user (i.e. use them just like you would call functions).

bruce343434 4y ago
> Try 4096x4096 Where should I, if we keep the context of OpenGL? Apart from that, I consider this an implementation issue. My post was mostly about keeping a consistent "front end" semantics. However the compiler or library transforms the data does not pertain to it. To be fair, I mentioned memory layout. If I had left that out, would we agree with eachother?
- dannymi 4y ago
  (Column|Row) Vectors and matrices are abstractions, and having abstractions that are always the same API in all of programming (not just OpenGL) would be nice. Of course making them again and again different and dumb is easier. So we got a lot of programs with weird arrays with no information on what matrix is what style. And thus readers get confused because half the information is missing in the source code! That makes things needlessly obtuse. But let's say one would try to make the API for column vectors (resp row vectors resp matrices) always the same (OpenGL or not), then it's important to look at bigger matrices. Otherwise you wouldn't care about storage layout at all and that's gonna come back to bite you in the ass (several orders of magnitude slower than possible). >But when you define a matrix in most programming languages you can only really write it like this: mat = [ [1,2,3], [4,5,6], [7,8,9] ] I wouldn't repurpose arrays like that.

VyseofArcadia 4y ago

> Abstractly, a vector is neither a row nor a column. An n-dimensional vector is an ordered collection of n coordinates. An m by n matrix is an m-dimensional vector of n-dimensional vectors. Oh we can get more abstract than that. A vector is an element of a vector space, or, if you'd like, an F-module where F is a field. A matrix is a homomorphism between vector spaces.

panda-giddiness 4y ago
To give an explicit example that breaks the column-vector mold: the set of 2x2 matrices with real entries forms a vector space, where each vector is a 2x2 matrix.
- VyseofArcadia 4y ago
  Let's get even weirder and leave finite dimensions behind. The set of sequences of complex numbers z_n such that the infinite sum from i = 1 to infinity of |z_i|^2 converges.