6
votes
Accepted
Ways to solve $Ax=b$ for a sparse (banded) $A$ with updates
If the only non-zero entries of $A_{ij}$ have $j$ in $\{i - 1, i, i + 1\}$, then $A$ is a banded matrix with bandwidth 1.
More generally, you can talk about matrices of bandwidth $k$ where $k$ is any ...
- 10.5k
4
votes
Are there any packaged routines (in lapack or elsewhere) for inverting a banded matrix?
Well, other than the usual "don't invert your matrices unless you need the inverse itself" you can still use the banded routines ?gbtrf and then use ...
- 393
2
votes
Accepted
Solving systems of linear equations with cyclic bidiagonal matrix
The special structure of your matrix is easily exploited by a custom made
$QR$ factorization based on Givens rotations. This leads to a method of $O(n)$ complexity. Below is a Octave/Matlab code, ...
- 591
2
votes
Accepted
Matlab backslash reordering algorithm
@gohokies has already given the correct answer in a comment, but just for more context: Matlab backslash calls the UMFPACK (now SuiteSparse) solver for sparse linear systems. The default ordering used ...
- 56.8k
2
votes
How to reorder variables to produce a banded matrix of minimum bandwidth?
There are many matrix reordering algorithms, and they seek a permutation array that maps from the original coordinates to the reordered coordinates.
Behrisch et al. (2016) gave a nice review of ...
- 121
2
votes
Accepted
Can a direct method like Thomas be used in a multigrid method as a smoother?
If you can solve the linear system with a direct solver, then that's exactly what you should be doing. Multigrid is a method that can be used if you don't have the time or memory resources to use a ...
- 56.8k
1
vote
Accepted
Solving triangular matrix equations on a GPU
1) Is there a mathematical trick to simplify the above matrix equations? As in, only having to do one inverse operation instead of two.
Yes: Schur complement formulation. Your system is equivalent to ...
- 12.6k
1
vote
TDMA with 3rd order upwind scheme
I would assume, that your $N\times N$ system has the following form:
$$
\underbrace{\begin{pmatrix}
b_1 & c_1 & & & & 0 \\
a_1 & b_2 & c_2 & &...
- 8,742
1
vote
Conservative formulation for compact finite difference schemes
The equation:
$$\partial_t f + \partial_xF = 0$$ with $f_{x=0} = f_0(t)$ (which is known) and appropiate initial conditions can be discretised as follows:
$$\partial_t\vec{f}+D\vec{F}=\vec{b}\tag{*}$$...
- 1,668
1
vote
Find a permutation matrix (using the Matlab's function $symrcm$) of a matrix $A(2:end, 2:end)$
From your comment "The plot emphasises expectedly the connections of node 1", I guess that maybe the idea is showing that node 1 is connected not only to a set of nodes that are "one close to the ...
- 12.6k
1
vote
solving tridiagonal system with multiple right hand sides
The most efficient way would likely be to perform one step of Gauss-Elimination on A to eliminate the sub-diagonal and then store the inverse of the new main diagonal, the new modified super-diagonal ...
- 127
1
vote
How to reorder variables to produce a banded matrix of minimum bandwidth?
While all the present answers are valid solutions to the practical problem, technically the answer to the question in your title (how to reorder variable to minimize bandwidth) is "it's an NP-complete ...
- 12.6k
Only top scored, non community-wiki answers of a minimum length are eligible