Suppose I have a square N X N symmetric real matrix A, and that I want to compute the LU decomposition of A. What is the complexity (e.g. O(N^2), O(N^3), etc...) of the best algorithm to do this
- If A is a dense matrix
- If A is a sparse matrix?
Suppose I have a square N X N symmetric real matrix A, and that I want to compute the LU decomposition of A. What is the complexity (e.g. O(N^2), O(N^3), etc...) of the best algorithm to do this
I would say it's the same order for sparse matrix multiplication as dense because (1) these order metrics only apply when the data is so large that the order effect dominates, and (2) sparsity at best reduces computation by a linear factor unrelated to the size N, therefore as N grows, but sparsity stays the same, the computation should again increase as O(N^3). As always, in the real world, your data size may not be large enough for this aspect of performance (the order) to dominate, and use of caches and optimized kernels will matter far more.
Wikipedia claims the following:
For a sparse matrix there is no single answer. It depends on the nature of the sparsity.