New answers tagged sparse-matrix
3
One such case is if the sparse matrix is banded. For example, tridiagonal linear systems can be solved in linear time using Thomas' algorithm. For small bandwidths, you can find an algorithm of linear time cost. Note that as the bandwidth grows, the hidden coefficient grows too.
The literature on the topic is active and there are many characterizations as ...
1
You have found Cuthill McKee, but there is also the "minimum degree" method as well as a bunch of others. Here are some considerations.
You state that these method improve caching. Well, this stuff was invented long before there were caches. The actual motivation for Cuthill McKee is reduction of the bandwidth.
You ask about iterative methods: ...
3
For direct factorization, you would ideally want to minimize the total fill-in. However, this is an NP-Hard combinatorial optimization problem that is intractable to solve for matrices of interesting size. Reducing the bandwidth does reduce an upper bound on the fill-in, which is a surrogate for what you really want.
In iterative methods, incomplete LU ...
2
When using an iterative method, you will typically use a preconditioner that speeds up convergence. A good example is the incomplete LU factorization (ILU).
When you take the LU factorization of a sparse matrix, the L and U factors might lose some of its sparsity, the extra entries are called fill in. The ILU will ignore some of this fill in to form a ...
Top 50 recent answers are included
