Fantastic post; I'm not much of a mathemetician, but the writing and logical progression were so clearly articulated, I was able to follow the gist the whole way through. Kudos!
It's nice to see some high-performance linear algebra code done in a modern lanugage! Would love to see more!
Is your approach specific to the case where the matrix fits inside cache, but the memory footprint of the basis causes performance issues? Most of the communication-avoiding Krylov works I've seen, e.g [0,1] seem to assume that if the matrix fits, so will its basis, and so end up doing some partitioning row-wise for the 'large matrix' case; I'm curious what your application is.
How accurate is this two-pass approach in general? From my outsider's perspective, it always looked like most of the difficulty in implementing Lanczos was reorthogonalization, which will be hard to do with the two-pass algorithm.
Or is this mostly a problem when you actually want to calculate the eigenvectors themselves, and not just matrix functions?
Or more precisely, lukefreed.xyz has NS records pointing to ns[1234].afraid.org, and the DNS servers for _afraid.org_ are subtly misconfigured (one of the six nameservers for afraid.org is evergreen.v6.afraid.org, and since you are trying to look up something in afraid.org but you already trying to resolve afraid.org, you'll need some extra “glue records” as part of the NS response, which is missing for that specific server).
8 comments
[ 3.0 ms ] story [ 28.1 ms ] threadWhat are you using this for and why are you working on it?
I admit I'm not personally convinced of the value of Rust in numerics, but that's just me, I guess...
May I ask what you've used to confirm the cache hit/miss rate? Thanks!
I hope you get your pay day, your blog is great!
Is your approach specific to the case where the matrix fits inside cache, but the memory footprint of the basis causes performance issues? Most of the communication-avoiding Krylov works I've seen, e.g [0,1] seem to assume that if the matrix fits, so will its basis, and so end up doing some partitioning row-wise for the 'large matrix' case; I'm curious what your application is.
[0] https://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-..., e.g. page 25. [1] https://www2.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-...
Or is this mostly a problem when you actually want to calculate the eigenvectors themselves, and not just matrix functions?
https://dns.squish.net/traverses/de494a9fe3310415f30369a9cb1...
Or more precisely, lukefreed.xyz has NS records pointing to ns[1234].afraid.org, and the DNS servers for _afraid.org_ are subtly misconfigured (one of the six nameservers for afraid.org is evergreen.v6.afraid.org, and since you are trying to look up something in afraid.org but you already trying to resolve afraid.org, you'll need some extra “glue records” as part of the NS response, which is missing for that specific server).