Name
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1109/MCSE.2005.117 | Computing in Science and Engineering |
Keywords | Field | DocType |
Lyapunov matrix equations,Poisson equation,eigenvalues and eigenfunctions,linear systems,Poisson equation,Sylvester equations,fast solver,large sparse systems,linear equations,matrix algebra,Poisson,decomposition,eigenvalues | Discrete mathematics,Combinatorics,Poisson's equation,Linear system,Sparse matrix,Eigenvalues and eigenvectors,Mathematics,Power of two,Computational complexity theory,Computation,Cholesky decomposition | Journal |
Volume | Issue | ISSN |
7 | 6 | 1521-9615 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| O'Leary, Dianne P. | 1 | 1064 | 222.93 |