3 ms·

weird to talk about linear algebra and never invoke linearity. also, why say these 2 things? >If you forget how matrix-vector multiplication works, just remem

weird to talk about linear algebra and never invoke linearity. also, why say these 2 things? >If you forget how matrix-vector multiplication works, just remember that its definition flows out of the notation. >Another way to think of matrix-vector multiplication is by treating each row of a matrix as its own vector, and computing the dot products of these row vectors with the vector we’re multiplying by. How on earth does that work?! What does vector similarity have to do with linear equations, or with matrix-vector multiplication? But you just told me to plug into the definition? Which is a dot product. Pretty incoherent.

ak_111 3y ago
IMO it is much clearer to justify something like matrix multiplication via a simple real life example like markov chain computations, it might add a bit of complexity in understanding the application but motivates the definition much better.
stOneskull 3y ago
i think it's a rushed draft it hasn't gone through a spell-checker, with words in there like hight and strage
adrian_b 3y ago
True. Moreover, here as in most other writings about linear algebra that I have seen, there is the very bad habit of describing the more complex operations as being composed from dot products. On modern CPUs, dot products must be avoided, because like all reduction operations they consist of one chain of dependent operations, so their speed is limited by the latency of the fused multiply-add operations, instead of being limited by the much higher throughput of the FMA operations. When vectors are multiplied with vectors, there is no alternative for dot products, so the only way to accelerate them is to reorder the operations into a tree, to be able to overlap a part of them, which are independent. When arrays with more dimensions are multiplied, e.g. matrices with vectors or matrices with matrices, the multiplications correspond with nested for loops, i.e. 2 nested loops for matrix-vector multiplication and 3 nested loops for matrix-matrix multiplication. The nested loops can be reordered arbitrarily. In each case, one of the possible loop orders has in the innermost loop the computation of a dot product. This is the only order mentioned in the parent article and in most other linear algebra manuals. However, this order is exactly the worst possible computationally. For 2 or more nested loops, there is always another order where the innermost operation is a so-called AXPY operation (the BLAS function name). AXPY means the scalar A multiplied by the vector X Plus the vector Y, with the result stored in Y. AXPY operations are always better than dot products, because the FMA operations are independent, so they can be pipelined, but for 3 or more nested loops there are better orders, where the innermost loop needs much less load and store operations than for AXPY. For 3 or more nested loops, there is always an order where the innermost operation is a tensor product of 2 vectors. This is a more attractive operation than both AXPY and dot products. If the tensor product of 2 vectors with N elements is stored in registers, then its computation needs N+N loads from memory, but N*N FMA operations, so if there are enough registers so that N>2, there will be much more FMA than loads, allowing the full utilization of the execution units of a modern CPU. In conclusion, matrix-vector products must not be described as being composed of N dot products that are executed separately for each element of the result vector, but as being the sum of N AXPY operations, which are accumulated into the result vector. Similarly, a matrix-matrix product must not be described as being composed of N^2 dot products, one for each element of the result matrix, but as being the sum of N vector-vector tensor products, which are accumulated into the result matrix. Such descriptions would be much more useful in practice, where the definitions based on dot products are just a hindrance.

ak_111 3y ago

IMO it is much clearer to justify something like matrix multiplication via a simple real life example like markov chain computations, it might add a bit of complexity in understanding the application but motivates the definition much better.

stOneskull 3y ago

i think it's a rushed draft it hasn't gone through a spell-checker, with words in there like hight and strage

adrian_b 3y ago

True. Moreover, here as in most other writings about linear algebra that I have seen, there is the very bad habit of describing the more complex operations as being composed from dot products. On modern CPUs, dot products must be avoided, because like all reduction operations they consist of one chain of dependent operations, so their speed is limited by the latency of the fused multiply-add operations, instead of being limited by the much higher throughput of the FMA operations. When vectors are multiplied with vectors, there is no alternative for dot products, so the only way to accelerate them is to reorder the operations into a tree, to be able to overlap a part of them, which are independent. When arrays with more dimensions are multiplied, e.g. matrices with vectors or matrices with matrices, the multiplications correspond with nested for loops, i.e. 2 nested loops for matrix-vector multiplication and 3 nested loops for matrix-matrix multiplication. The nested loops can be reordered arbitrarily. In each case, one of the possible loop orders has in the innermost loop the computation of a dot product. This is the only order mentioned in the parent article and in most other linear algebra manuals. However, this order is exactly the worst possible computationally. For 2 or more nested loops, there is always another order where the innermost operation is a so-called AXPY operation (the BLAS function name). AXPY means the scalar A multiplied by the vector X Plus the vector Y, with the result stored in Y. AXPY operations are always better than dot products, because the FMA operations are independent, so they can be pipelined, but for 3 or more nested loops there are better orders, where the innermost loop needs much less load and store operations than for AXPY. For 3 or more nested loops, there is always an order where the innermost operation is a tensor product of 2 vectors. This is a more attractive operation than both AXPY and dot products. If the tensor product of 2 vectors with N elements is stored in registers, then its computation needs N+N loads from memory, but N*N FMA operations, so if there are enough registers so that N>2, there will be much more FMA than loads, allowing the full utilization of the execution units of a modern CPU. In conclusion, matrix-vector products must not be described as being composed of N dot products that are executed separately for each element of the result vector, but as being the sum of N AXPY operations, which are accumulated into the result vector. Similarly, a matrix-matrix product must not be described as being composed of N^2 dot products, one for each element of the result matrix, but as being the sum of N vector-vector tensor products, which are accumulated into the result matrix. Such descriptions would be much more useful in practice, where the definitions based on dot products are just a hindrance.