5 ms·
I've recently had the following idea that might make making new linear algebra libraries like this one easier. There might be some overlap with the ideas in the
by ogogmad 4y ago
I've recently had the following idea that might make making new linear algebra libraries like this one easier. There might be some overlap with the ideas in the article, but generalised.
Assume you've got a routine for unitarily diagonalising a self-adjoint matrix with entries in the complex numbers. Call the resulting decomposition the spectral decomposition.
Now imagine keeping that same routine, but changing the complex numbers to other *-algebras. That means redefining what the operations {plus,times,minus,div,conjugate} do, while keeping the algorithm the same.
The observation is that for one choice of *-algebra, the spectral decomposition changes to the SVD, and an SVD-algorithm is obtained directly. For another *-algebra, the spectral decomposition changes to the Takagi decomposition, and a Takagi-algorithm is obtained directly.
The above uses operator overloading to turn one matrix decomposition into another.
- adamnemecek 4y agoYeah I have been realizing this lately as well. I have written up a bit on this https://github.com/adamnemecek/adjoint/ https://github.com/adamnemecek/adjoint/ Check the raw source there’s a bunch of links. Fixed points, diagonalizations and eigenshit are all the same thing.
- ogogmad 4y agoWhat I'm suggesting doesn't appear to be mentioned there.
- adamnemecek 4y agoThe thing that makes it tick is adjoint and norm.
- elcritch 4y agoInteresting, I learned recently the reason that Galois fields are so important in error correction codes (and encryption) is that they enable invertable matrix operations using integers which makes them easy compute in dedicated hardware. Apparently development of the error correction codes used on CDs wouldn't have been feasible with the computing power of the time without being able to build custom silicon for it.
- JadeNB 4y ago> Fixed points, diagonalizations and eigen… are all the same thing. This is true in a moral sense, but not literally. Fixed points are eigenvectors for a particular eigenvalue \lambda = 1 (together with the 0 vector, which is always fixed but not an eigenvector, by fiat). (Over a field,) eigenvectors corresponding to non-0 eigenvalues are not fixed points, although they lie on fixed lines; and they can be made fixed points by re-scaling the original matrix, if that is convenient. I don't know an obvious way to think of eigenvectors with eigenvalue \lambda = 0 as fixed vectors. A matrix that is diagonalizable has sufficiently many eigenvectors, but a matrix may have eigenvectors even if it is not diagonalizable.
- haskellandchill 4y agoEigenvectors for eigenvalue 0 characterize the null space. The eigenvalue 0 can have a multiplicity of eigenvectors, these eigenvectors span the nullspace.
- bigbillheck 4y agoYou might be interested in GraphBLAS: https://graphblas.org https://graphblas.org
- throwawaymaths 4y agoIs this not basically what julialang does?
- reikonomusha 4y agoA lot of the trouble of implementing numerical linear algebra is getting decent performance and numerical stability using finite-precision operations with bounded numerical representations. How do you think this sort of generalized approach would work if you want things to behave nicely with, say, poorly conditioned matrices, or matrices with certain structure that might get clobbered when changing to another algebra? Are these things even necessary to consider in such a design? Or would this direction be mostly for bootstrapping a functional—but perhaps not performant or numerically stable—library?