4 ms·
Nice list. I would add 8. [edit: oops that's already no 5] Not taking advantage of matrix structure (symmetric, sparse, banded, Toeplitz, ...) 9. Transposing
by sieste 4y ago
Nice list. I would add
8. [edit: oops that's already no 5] Not taking advantage of matrix structure (symmetric, sparse, banded, Toeplitz, ...)
9. Transposing a matrix (Like the inverse A^{-1}, the explicit transpose A^t is often not needed)
- adgjlsfhk1 4y agoIMO 9 is the fault of the language rather than the programmer. Julia solves this one by having types that can represent conjugates, transposes, and adjoints of arbitrary matrices lazily.
- SuchAnonMuchWow 4y agoand in python/numpy, transpose is a O(1) operation: it doesn't actually move any data, just changes the strides used to access data points in the underlying buffer.
- bee_rider 4y agoI think they are talking about explicitly transposing it in memory here. A "transpose operation flag" is pretty a standard feature for linear algebra libraries. If someone is writing a higher level object-oriented linear algebra environment, having the matrices carry around a "transposed" flag that they can pass to BLAS seems like a reasonable thing to do. Since, other than in Julia and Matlab, matrix stuff is usually an add-on, we can't really blame the language for this decision IMO. A downside could be -- usually your underlying tuned library will be BLAS and LAPACK, which don't accept a 'transposed' flag for every single operation. So, from the user point of view, it could be kind of confusing -- "when I transpose a matrix and then go on to multiply, the transpose is free. But if I transpose a matrix and then go on to hit it with QR, it for some reason incurs this weird extra cost -- not where I do the operation, but later, in the QR."
- SuchAnonMuchWow 4y ago> 8. Not taking advantage of matrix structure (symmetric, sparse, banded, Toeplitz, ...) This is the sin no 5 of the article: "5. Not Exploiting Structure in the Matrix"
- stncls 4y ago> 9. Transposing a matrix ... if you only use the transpose once. If instead it is going to be used multiple times, explicitly computing the transpose can be a huge performance boost. For dense matrices, it is typically used to exploit memory locality (i.e. to be prefetch- and cache-friendly). For sparse matrices (your point 8), the advantage can be even more pronounced, sometimes the difference between being able to exploit sparsity, or not.
- jcranmer 4y ago> 9. Transposing a matrix (Like the inverse A^{-1}, the explicit transpose A^t is often not needed) Most matrix libraries should make transpose, conjugate, and conjugate transpose just twiddling a bit on its internal representation--BLAS routines should have a parameter on them saying if the input matrix needs to be transposed and/or conjugated before doing an operation.
- joppy 4y agoDoesn’t memory layout still matter? Assumedly matrix-vector products like Av are fastest if the rows of A are contiguous in memory, and vector-matrix products vA are fastest when the columns are contiguous in memory. So sometimes one would really want to actually transpose the matrix, rather than reinterpreting the indexing scheme.
- dekhn 4y agoMaterializing the transpose of a matrix is one of the most common and useful operations at the start of a large-scale data processing system. People who say "transpose is an O(1) operation because it just creates a view" aren't including the important detail of caches and access patterns impact on performance.