Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [banded-matrix]

Referring to sparse matrices with concentrations of non-zero elements along a combination of diagonals, subdiagonals, and/or superdiagonals.

2
votes
0answers
81 views

Can I take advantage of a nearly banded A in AX=b?

I am working on a 1D drift-driffusion problem in a finite-difference (FD) approach. I hade 3 equations per node ($3N$ in total): electron continuity $E_i$, Poisson $P_i$, hole continuity $H_i$. With ...
1
vote
1answer
71 views

TDMA with 3rd order upwind scheme

I'm trying to implement a model I found in a paper, but there is something I do not understand. The authors say they use TDMA to solve their equations; however, they use a 3rd order upwind biased ...
1
vote
1answer
191 views

Ways to solve $Ax=b$ for a sparse (banded) $A$ with updates

I want to solve the time-dependent Schrodinger Equation using the Crank-Nicolson scheme. I end up with the following matrix equation ...
0
votes
2answers
103 views

Conservative formulation for compact finite difference schemes

At the Section 4.2 of this paper (which is very well known in the computational fluid dynamic community), the author claims that it is enough, for the compact finite difference formulation in eq. 4.2....
0
votes
1answer
58 views

Matlab backslash reordering algorithm

For the linear system $\mathbf A \mathbf x = \mathbf b$ generated from 2D Poisson equation using the standard central finite difference method, $$ \mathbf A = \begin{bmatrix} \mathbf K & -\mathbf ...
0
votes
1answer
82 views

Are there any packaged routines (in lapack or elsewhere) for inverting a banded matrix?

I have a matrix of the form And I would like to invert it. Currently I am using the lapack routines zgetrf and zgetri. I.e. I am performing LU factorisation. My question: Are there any packaged ...
3
votes
0answers
143 views

Fast solution of a heptadiagonal linear system

I have a linear system of the form $\mathbf{A}\mathbf{x} = \mathbf{f}$. If the length of the vector $\mathbf{x}$ is $N$, meaning that there are $N$ unknowns, then the matrix $\mathbf{A}$ has seven ...
5
votes
2answers
169 views

Solving systems of linear equations with cyclic bidiagonal matrix

I am looking for a good numerical method to solve a linear system (of small/moderate size) with a matrix of the form $$ \begin{bmatrix} a_1 & b_1\\ & a_2 & \ddots \\ & & \ddots &...
1
vote
2answers
419 views

Find a permutation matrix (using the Matlab's function $symrcm$) of a matrix $A(2:end, 2:end)$

I've the following Matlab code: r = symrcm(A(2:end, 2:end)); prcm = [1 r + 1]; spy(A(prcm, prcm)); where A should be sparse ...
5
votes
1answer
131 views

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

Given a symmetric matrix $A$, the Lanczos algorithm outputs $C$ such that $C^{T}AC$ is tridiagonal. Is there a generalization of this such that $C^{T}AC$ is banded of specific width $w$? Note that $C$...
0
votes
1answer
160 views

solving tridiagonal system with multiple right hand sides

I need to solve a tridiagonal system (positive definite, diagonally dominant) $Ax = b$ in a time stepping loop. $A \in \mathbb{R}^{N \times N}$ remains constant but $b$ changes during each time ...
1
vote
1answer
69 views

Creating a matrix that saves storage

Suppose $A\in\mathbb{R}^{n\times n}$ is a banded matrix, i.e., a matrix with all of its nonzero elements on the main diagonal, i.e., $\alpha_{i,i}\neq 0$, the first superdiagonal, i.e., $\alpha_{i,i+1}...
2
votes
0answers
49 views

Fast library for parallel n-diagonal matrix inversion

I've tried looking for efficient parallel algorithms to solve banded systems. SPIKE is a good example but it however requires that the band size is large. Is there any efficient library implementing ...
1
vote
1answer
379 views

Why does `symrcm` create larger band width?

When I run the following (in Matlab) on a sparse matrix $A$, I get larger band width. The symrcm (symmetric reverse Cuthill-McKee permutation) is not guarenteed to ...
5
votes
1answer
83 views

Is the bandwidth of indefinite A equal to its factor L in LDL^T?

In George, Liu, and Ng's book Computer Solutions of Sparse Linear Systems, it has been shown that bandwidth of $A$ is equal to bandwidth of its factors in $LL^T$.(section 4.3) However, I guess this is ...
1
vote
1answer
114 views

large symmetric positive band matrix

I use gpbsv command from Intel MKL to solve symmetric positive band system. But unfortunately when the system is large I get an error Access violating writing location in VisualStudio. Could someone ...
1
vote
0answers
127 views

Algorithms to compute largest gap between smallest nonzero eigenvalues of sparse symmetric matrix

I am looking mainly for c/c++ implementations but also for theoretical algorithms to compute gaps between smallest positive eigenvalues of symmetric, singular matrix or real numbers. To be precise, I ...
7
votes
1answer
2k views

full rank update to cholesky decomposition

Let $A$ be a real, symmetric, positive definite matrix. It has at least 500 rows, possibly much more. I compute its Cholesky decomposition, which allows me to calculate $det(A)$ $A^{-1}X$ for some ...
2
votes
1answer
444 views

how to use lanczos code from netlib for large sparse symmetric matrix?

I want to use lanczos method to calculate the few lowest eigenvalue and eigen-vector of a large sparse symmetric matrix(~50k x ~50k). In http://www.netlib.org/lanczos/index.html I found the codes ...
1
vote
1answer
2k views

what is difference “DSYEV(LAPACK SUBROUTINE)” and “Lanczos”?

I am working on Fermion and Boson Hubbard Models, in which the dimension of Hilbert Spaces are quite large (~50k). Because the Hamiltonian matrix is ~50k X ~50k, to diagonalize these big sparse ...
3
votes
2answers
589 views

Efficient computation of Markov chain transition probability matrix

Consider a continuous Markov chain $X=(X_t)$ on a finite state space and let $Q$ be the (given) transition rate matrix. This matrix is very sparse, with non-zero values on 3 diagonals only (so from ...
15
votes
2answers
15k views

Writing the Poisson equation finite-difference matrix with Neumann boundary conditions

I am interested in solving the Poisson equation using the finite-difference approach. I would like to better understand how to write the matrix equation with Neumann boundary conditions. Would someone ...
4
votes
2answers
1k views

How should I build a 2D 5-point stencil Laplacian matrix in parallel?

I'm making a simple eigenvalue solver with SLEPc, using a 5-point stencil and the finite difference method. I want to be able to assemble the matrix in parallel. My first thought was just to use <...
8
votes
1answer
3k views

How does LAPACK solve tridiagonal systems and why

In my project I have to solve a couple of tridiagonal matrices at every time step, so it is crucial to have a good solver for those. I did my own implementation, just the classical way to do it ...
5
votes
2answers
452 views

What heuristics can be used to minimize the asymptotic matrix bandwidth of a 5-point Laplacian discretization?

I can see that there are multiple heuristics to achieve a matrix with minimum bandwidth. As heuristics, they can't guarantee an optimal solution in polynomial time (after all, the problem is NP-...
15
votes
4answers
1k views

How to reorder variables to produce a banded matrix of minimum bandwidth?

I'm trying to solve a 2D Poisson equation by finite differences. In the process, I obtain a sparse matrix with only $5$ variables in each equation. For example, if the variables were $U$, then the ...
5
votes
2answers
458 views

How to parallelize a banded direct solver?

I have a linear system whose matrix that is diagonally dominant, non-symmetric, but banded. Since the band-radius is 2 (producing only 5 variables per equation), a banded direct solver (gaussian ...