Abstract :
We´re using the structure of a problem with n2 unknowns to reduce the amount of computation from O(n6) (using the Cholesky decomposition) to O(n4) (exploiting sparsity) and then to O(n3) (using the Sylvester structure), a substantial savings when n is large. But knowing just a bit more about the problem´s structure allows further reduction, down to O(n2 log2n) when n is a power of two. Because we´re computing n2 answers, this is close to optimal, and it illustrates the value of exploiting every possible bit of structure in our problems.
Keywords :
Lyapunov matrix equations; Poisson equation; eigenvalues and eigenfunctions; linear systems; Poisson equation; Sylvester equations; fast solver; large sparse systems; linear equations; matrix algebra; Arithmetic; Computational efficiency; Eigenvalues and eigenfunctions; Equations; Gold; Home computing; Linear systems; Matrix decomposition; Sparse matrices; Sufficient conditions; Poisson; decomposition; eigenvalues;
