Skip to main content
7 votes

Solve for $C$ such that $C^{T}AC$ is banded of given width

Yes. The block Lanczos algorithm http://www.netlib.org/utk/people/JackDongarra/etemplates/node250.html produces a block triangular matrix where you control the block size, hence the bandwidth. ...
Carl Christian's user avatar
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 ...
Daniel Shapero's user avatar
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 ...
percusse's user avatar
  • 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, ...
wim's user avatar
  • 571
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 ...
Wolfgang Bangerth's user avatar
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 ...
AlexM's user avatar
  • 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 ...
Wolfgang Bangerth's user avatar
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 ...
Federico Poloni's user avatar
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 & &...
Anton Menshov's user avatar
  • 8,672
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{*}$$...
HBR's user avatar
  • 1,648
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 ...
Federico Poloni's user avatar
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 ...
DrHansGruber's user avatar
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 ...
Federico Poloni's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible