New Method for Solving Linear Systems

[Puzzle-Peter]

I'd love to see what this method can do with large problems. I do FEM calculations and some of the systems I'm dealing with are >10M variables. They take quite some time even on really powerful machines.

Those matrices are populated very sparsely, so as far as I understand (which is not far at all) this new method wouldn't give much benefit as there are already highly optimized methods for these problems? Our running times roughly correlate with the square of the problem size.

[Dubslow]

Originally Posted by Puzzle-Peter

I'd love to see what this method can do with large problems. I do FEM calculations and some of the systems I'm dealing with are >10M variables. They take quite some time even on really powerful machines.

Those matrices are populated very sparsely, so as far as I understand (which is not far at all) this new method wouldn't give much benefit as there are already highly optimized methods for these problems? Our running times roughly correlate with the square of the problem size.

You're mostly right. My initial test case is a relatively small 250K matrix, and under the N as defined in the paper, the total memory of the "test vectors" is around 2 TB. I'm working on optimizing the memory use as much as possible, but there's no way to work around the fact that N will always be limited to much much much less than described in the paper. That and the fact that the complexity is O(n³) lead me to believe this will never be practically useful, but I'll keep trying at it. (As pointed out above, the Block Lanczos/Wiedemann algos are roughly O(n²), as you suggest.)

By the way jasonp (or others with the answer), because the matrix is sparse, doesn't that mean that the solution vectors are around as sparse? That would go a long way to reducing the memory requirement.

[jasonp]

If you did GE on the matrix and wound up with a few variables that have no dependencies, setting those few variables to random bits and back-propagating will produce a completely dense nullspace solution. Setting those few variables to mostly zeros will also lead to a dense solution because the matrix mixes the mostly-zeros very thoroughly, but then you risk the Lanczos iteration failing.

The bound in the paper would mean a matrix of size n with elements in GF_2 needs 400n trial vectors to generate a solution with high probability. FEM calculations don't benefit at all because the method as written only applies to matrices with elements in a finite field.