LU Decomposition N^3

Question

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?

Answer 1

Wikipedia claims the following:

If two matrices of order n can be multiplied in time M(n), where M(n)≥na for some a>2, then the LU decomposition can be computed in time O(M(n)). This means, for example, that an O(n^2.376) algorithm exists based on the Coppersmith–Winograd algorithm.

For a sparse matrix there is no single answer. It depends on the nature of the sparsity.

Answer 2

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.