Hubbry Logo
search
logo
Band matrix avatar
Band matrix
Band matrix
current hub
B

Band matrix

logo
Community Hub0 Subscribers
Read side by side
Band matrix
View on Wikipedia
from Wikipedia

In mathematics, particularly matrix theory, a band matrix or banded matrix is a sparse matrix whose non-zero entries are confined to a diagonal band, comprising the main diagonal and zero or more diagonals on either side.

Band matrix

[edit]

Bandwidth

[edit]

Formally, consider an n×n matrix A=(ai,j ). If all matrix elements are zero outside a diagonally bordered band whose range is determined by constants k1 and k2:

then the quantities k1 and k2 are called the lower bandwidth and upper bandwidth, respectively.[1] The bandwidth of the matrix is the maximum of k1 and k2; in other words, it is the number k such that if .[2]

Examples

[edit]

Applications

[edit]

In numerical analysis, matrices from finite element or finite difference problems are often banded. Such matrices can be viewed as descriptions of the coupling between the problem variables; the banded property corresponds to the fact that variables are not coupled over arbitrarily large distances. Such matrices can be further divided – for instance, banded matrices exist where every element in the band is nonzero.

Problems in higher dimensions also lead to banded matrices, in which case the band itself also tends to be sparse. For instance, a partial differential equation on a square domain (using central differences) will yield a matrix with a bandwidth equal to the square root of the matrix dimension, but inside the band only 5 diagonals are nonzero. Unfortunately, applying Gaussian elimination (or equivalently an LU decomposition) to such a matrix results in the band being filled in by many non-zero elements.

Band storage

[edit]

Band matrices are usually stored by storing the diagonals in the band; the rest is implicitly zero.

For example, a tridiagonal matrix has bandwidth 1. The 6-by-6 matrix

is stored as the 6-by-3 matrix

A further saving is possible when the matrix is symmetric. For example, consider a symmetric 6-by-6 matrix with an upper bandwidth of 2:

This matrix is stored as the 6-by-3 matrix:

Band form of sparse matrices

[edit]

From a computational point of view, working with band matrices is always preferential to working with similarly dimensioned square matrices. A band matrix can be likened in complexity to a rectangular matrix whose row dimension is equal to the bandwidth of the band matrix. Thus the work involved in performing operations such as multiplication falls significantly, often leading to huge savings in terms of calculation time and complexity.

As sparse matrices lend themselves to more efficient computation than dense matrices, as well as in more efficient utilization of computer storage, there has been much research focused on finding ways to minimise the bandwidth (or directly minimise the fill-in) by applying permutations to the matrix, or other such equivalence or similarity transformations.[3]

The Cuthill–McKee algorithm can be used to reduce the bandwidth of a sparse symmetric matrix. There are, however, matrices for which the reverse Cuthill–McKee algorithm performs better. There are many other methods in use.

The problem of finding a representation of a matrix with minimal bandwidth by means of permutations of rows and columns is NP-hard.[4]

See also

[edit]

Notes

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Band matrix

View on Grokipedia
from Grokipedia
A band matrix is a square matrix whose non-zero entries are confined to a diagonal band consisting of the main diagonal and a limited number of adjacent superdiagonals and subdiagonals, with all other entries being zero.[1] This structure makes it a type of sparse matrix, where the bandwidth—defined by the lower bandwidth p (number of subdiagonals) and upper bandwidth q (number of superdiagonals)—determines the extent of the non-zero region, such that aij = 0 if i > j + p or j > i + q.[2] For instance, a tridiagonal matrix is a special case with p = q = 1, featuring non-zeros only on the main diagonal and the immediate adjacent diagonals.[1] Band matrices frequently arise in the discretization of partial differential equations (PDEs) using finite difference or finite element methods, as well as in applications like circuit analysis and optimization problems, where the underlying physical or mathematical structure limits interactions to nearby elements.[3][4][5] Their sparsity enables significant computational efficiencies; for example, the LU factorization of a band matrix with bandwidths p and q requires only O(n p q) arithmetic operations—linear in the matrix dimension n for fixed p and q—compared to O(n3) for a dense matrix, while preserving the banded structure in the factors L and U.[6] This property underpins specialized algorithms, such as the Thomas algorithm for tridiagonal systems, which solve linear equations in O(n) time and are widely used in numerical analysis for solving banded linear systems.[6]

Fundamentals

Definition

A band matrix is a square matrix whose non-zero entries are confined to a diagonal band comprising the main diagonal and a limited number of adjacent subdiagonals and superdiagonals. Formally, for an $ n \times n $ matrix $ A = (a_{ij}) $, $ A $ has lower bandwidth $ p $ and upper bandwidth $ q $ if $ a_{ij} = 0 $ whenever $ i > j + p $ or $ j > i + q $, where $ p $ and $ q $ are non-negative integers.[7] The main diagonal consists of the entries $ a_{ii} $ for $ i = 1, \dots, n $, while the subdiagonals (below the main diagonal) and superdiagonals (above it) form the band's extent, with all entries outside this region being zero. This structured sparsity arises naturally in applications involving discretized differential equations, where the band's width reflects the order of the discretization.[8] Band matrices differ from general sparse matrices in that their non-zero entries follow a predictable, contiguous pattern around the main diagonal rather than occurring in arbitrary positions.[1] Visually, a band matrix appears as a central strip of potential non-zero values flanked by blocks of zeros in the corners, as illustrated in the following generic example for a matrix with $ p = 1 $ and $ q = 2 $: $$ \begin{pmatrix}
  • & * & * & 0 & 0 \
  • & * & * & * & 0 \ 0 & * & * & * & * \ 0 & 0 & * & * & * \ 0 & 0 & 0 & * & * \end{pmatrix} $$
where $ * $ denotes possible non-zero entries.[7]

Bandwidth

In a band matrix A=(ai,j)A = (a_{i,j}), the lower semi-bandwidth pp is defined as the smallest non-negative integer such that ai,j=0a_{i,j} = 0 whenever i>j+pi > j + p, meaning all non-zero entries below the main diagonal are confined to at most the pp subdiagonals. Similarly, the upper semi-bandwidth qq is the smallest non-negative integer such that ai,j=0a_{i,j} = 0 whenever j>i+qj > i + q, restricting non-zero entries above the main diagonal to at most the qq superdiagonals. These semi-bandwidths quantify the sparsity of the matrix by measuring the extent of the non-zero band around the diagonal.[9] The total bandwidth bb of the matrix is then given by b=p+q+1b = p + q + 1, representing the total number of diagonals (including the main diagonal) that may contain non-zero entries. Another common formulation defines the bandwidth as b=max⁡{∣i−j∣:ai,j≠0}b = \max \{ |i - j| : a_{i,j} \neq 0 \}, which aligns with the maximum distance from the main diagonal to any non-zero entry and equals max⁡(p,q)\max(p, q). These measures are fundamental for assessing the sparsity and enabling efficient storage and computation for band matrices.[10] To minimize the bandwidth of a sparse matrix, which can improve numerical algorithms by reducing the effective sparsity pattern, reordering techniques are employed. The reverse Cuthill-McKee (RCM) algorithm, a refinement of the original Cuthill-McKee method, achieves this by permuting the rows and columns to cluster non-zero entries closer to the diagonal, thereby decreasing the semi-bandwidths and total bandwidth while aiming to limit fill-in during factorizations. This reordering is particularly valuable in applications like finite element methods, where the initial matrix ordering from mesh connectivity may yield large bandwidths.[11]

Properties

Algebraic properties

Band matrices exhibit desirable algebraic properties under basic operations, preserving their sparse structure to varying degrees. The sum of two band matrices AA and BB, where AA has lower bandwidth pAp_A and upper bandwidth qAq_A, and BB has lower bandwidth pBp_B and upper bandwidth qBq_B, results in a band matrix with lower bandwidth max⁡(pA,pB)\max(p_A, p_B) and upper bandwidth max⁡(qA,qB)\max(q_A, q_B).[7] This preservation ensures that the sparsity pattern is maintained within the widest band of the operands. In contrast, the product ABAB of two band matrices yields a band matrix whose lower bandwidth is at most pA+pBp_A + p_B and upper bandwidth is at most qA+qBq_A + q_B.[7] For an m×nm \times n matrix AA with bandwidths pA,qAp_A, q_A multiplied by an n×kn \times k matrix BB with bandwidths pB,qBp_B, q_B, the product's bandwidths are bounded by min⁡(m−1,pA+pB)\min(m-1, p_A + p_B) for the lower and min⁡(k−1,qA+qB)\min(k-1, q_A + q_B) for the upper.[12] Symmetric band matrices, characterized by p=qp = q, possess additional structure that enhances their utility in numerical methods. Such matrices arise frequently in applications like finite difference discretizations and maintain symmetry under addition and multiplication by symmetric band matrices, with the resulting bandwidth following the rules above.[7] If a symmetric band matrix is positive definite, it admits a Cholesky factorization A=LLTA = LL^T, where LL is a lower triangular band matrix with the same lower bandwidth pp as AA, thus preserving the band structure without fill-in beyond the original bandwidth.[7] This property is particularly valuable for efficient computation, as the factorization requires O(np2)O(n p^2) operations compared to O(n3)O(n^3) for dense matrices.[7] Regarding rank and determinant, band matrices that are strictly diagonally dominant—meaning ∣aii∣>∑j≠i∣aij∣|a_{ii}| > \sum_{j \neq i} |a_{ij}| for each row—are nonsingular and thus have full rank nn for an n×nn \times n matrix.[13] The banded structure does not alter this nonsingularity condition, ensuring invertibility under diagonal dominance. For positive definite symmetric band matrices, the Cholesky factorization not only confirms full rank but also allows computation of the determinant as the product of the squares of the diagonal entries of LL, det⁡(A)=∏i=1n(lii)2>0\det(A) = \prod_{i=1}^n (l_{ii})^2 > 0.[7] This direct link between structure and determinant computation underscores the algebraic advantages of band matrices in ensuring well-conditioned operations.

Numerical stability in operations

Band matrices exhibit favorable numerical stability in common linear algebra operations due to their limited non-zero structure, which confines computations and reduces the propagation of rounding errors compared to dense matrices. In particular, the LU decomposition of a band matrix AA with lower bandwidth pp and upper bandwidth qq preserves the band structure, yielding a lower triangular factor LL with lower bandwidth pp and an upper triangular factor UU with upper bandwidth qq. This preservation minimizes storage and computational requirements, with the factorization requiring approximately 2npq2n p q floating-point operations for an n×nn \times n matrix where n≫p,qn \gg p, q.[14] During Gaussian elimination without pivoting, no fill-in occurs outside the original band, ensuring that the sparsity pattern is maintained exactly within the enlarged envelope of width p+q+1p + q + 1. This lack of extraneous fill-in contrasts sharply with dense matrices, where elimination can introduce O(n2)O(n^2) new non-zeros, and it directly contributes to numerical stability by limiting the scope of error accumulation. However, to enhance robustness against small pivots, partial pivoting is often employed, which may increase the effective bandwidth of UU to p+qp + q but still confines fill-in within a predictable envelope, with no additional non-zeros beyond the band structure.[14][15][15] The condition number of a band matrix, which measures sensitivity to perturbations, is often well-behaved when the matrix is diagonally dominant, as the limited off-diagonal elements restrict the growth of singular values. For example, diagonally dominant band matrices with constant diagonal entries (e.g., 100) and ones elsewhere in the band typically exhibit condition numbers between 1 and 3, indicating excellent numerical conditioning. Rounding errors in operations like LU factorization are bounded in terms of the bandwidth, with backward error analyses showing perturbations on the order of machine epsilon times the bandwidth-scaled norm of the matrix, thus scaling more gracefully than for full matrices.[16][16][14] For eigenvalue computations, symmetric tridiagonal band matrices (with p=q=1p = q = 1, total bandwidth 3) possess real eigenvalues, a direct consequence of the spectral theorem for symmetric matrices. The QR iteration applied to such matrices maintains the tridiagonal structure and converges stably, with each iteration requiring O(n)O(n) operations and numerical errors controlled by the orthogonal transformations inherent to the method. Specialized parallel QR variants further ensure stability for large-scale problems, delivering accurate eigenvalues with low communication overhead and work efficiency comparable to sequential implementations.[17][14][18]

Examples

Low-bandwidth matrices

Low-bandwidth matrices represent the simplest forms of band matrices, where the non-zero entries are confined to a narrow diagonal band, facilitating straightforward analysis and computation. These matrices are particularly useful for illustrating the core structure of band matrices due to their sparse nature and minimal fill-in during operations. A diagonal matrix is the most basic low-bandwidth example, possessing a bandwidth of $ b = 1 $, with all off-diagonal elements strictly zero such that $ a_{i,j} = 0 $ for $ i \neq j $.[19] In this form, the matrix consists solely of the main diagonal, making it exceptionally simple and equivalent to a collection of independent scalar entries.[8] Bidiagonal matrices extend this simplicity slightly, featuring a bandwidth of $ b = 2 $, where non-zero entries appear only on the main diagonal and one adjacent off-diagonal.[8] Upper bidiagonal matrices have non-zeros on the main and superdiagonal, while lower variants have them on the main and subdiagonal; this structure maintains sparsity while introducing limited coupling between consecutive elements.[20] Tridiagonal matrices, with a bandwidth of $ b = 3 $, allow non-zero entries on the main diagonal, the immediate subdiagonal, and the superdiagonal, creating a tight band that captures nearest-neighbor interactions.[8] A prominent example is the discrete Laplacian matrix arising from finite difference approximations of the second derivative in one dimension, typically of the form
[2−10⋯−12−1⋯0−12⋯⋮⋮⋮⋱], \begin{bmatrix} 2 & -1 & 0 & \cdots \\ -1 & 2 & -1 & \cdots \\ 0 & -1 & 2 & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix},
which models diffusion or heat equations on a grid.[21] These matrices exhibit unique properties, such as efficient inversion for tridiagonal cases using the Thomas algorithm, which performs forward elimination followed by backward substitution to solve systems in $ O(n) $ time.[22]

Higher-bandwidth cases

Pentadiagonal matrices represent a case of higher-bandwidth band matrices with a total bandwidth of 5, where non-zero entries are confined to the main diagonal and the two nearest subdiagonals and superdiagonals. These matrices commonly emerge in finite difference discretizations of partial differential equations, such as higher-order approximations for boundary value problems that achieve a truncation error of order h2h^2, resulting in systems that require solving pentadiagonal structures for improved accuracy in resolving solution features.[23] For a more general illustration, consider a 5×5 band matrix with lower bandwidth p=2p=2 (two subdiagonals) and upper bandwidth q=1q=1 (one superdiagonal), yielding a total bandwidth of 4. The non-zero entries are restricted such that aij=0a_{ij} = 0 if i−j>2i - j > 2 or j−i>1j - i > 1, producing a sparse structure like: $$ \begin{pmatrix}
  • & * & 0 & 0 & 0 \
  • & * & * & 0 & 0 \
  • & * & * & * & 0 \ 0 & * & * & * & * \ 0 & 0 & * & * & * \end{pmatrix} $$
where asterisks denote potentially non-zero elements; this layout demonstrates how the band confines sparsity while allowing asymmetry in the bandwidths, as detailed in standard treatments of unsymmetric band matrices.[7] Block band matrices extend the band structure by composing the matrix of blocks, where non-zero blocks are confined within a coarser band, making them suitable for structured problems like multidimensional discretizations in scientific simulations. For example, in queuing models or finite element methods for multi-dimensional problems, the overall matrix exhibits a block-banded form with each block itself potentially banded, enabling efficient handling of hierarchical sparsity.[24] Matrices with variable bandwidth, also known as skyline or profile matrices, allow the number of non-zero entries per row (effectively varying pp or qq) while maintaining an overall bounded envelope, arising in applications like finite element analysis where mesh connectivity leads to irregular profiles. In such cases, the skyline storage exploits the varying heights of the "skyline" formed by the first non-zero in each column, optimizing memory for problems with non-uniform structure without assuming a fixed band across all rows.

Applications

Linear algebra solvers

Band matrices arise frequently in the discretization of partial differential equations, leading to efficient solvers that exploit their sparse structure to solve linear systems Ax=bAx = b with reduced computational cost compared to dense matrix methods. Direct solvers, such as those based on LU decomposition, and iterative methods like the conjugate gradient algorithm, are particularly adapted to preserve the bandwidth during factorization or multiplication, achieving complexities that scale linearly or near-linearly with the matrix dimension nn and bandwidth parameters pp (lower) and qq (upper). These approaches avoid fill-in beyond the band, enabling storage and operations in O(n(p+q))O(n(p+q)) time and space. The Thomas algorithm, also known as the tridiagonal matrix algorithm (TDMA), provides an O(n)O(n) direct solution for tridiagonal systems where p=q=1p = q = 1. For a system Ax=bAx = b with tridiagonal matrix AA having subdiagonal entries aia_i, diagonal entries bib_i, and superdiagonal entries cic_i (for i=1,…,ni = 1, \dots, n), the algorithm performs forward elimination followed by backward substitution without pivoting. In the forward sweep, modified superdiagonal coefficients are computed as ci′=ci/di′c_i' = c_i / d_i' for i=1,…,n−1i = 1, \dots, n-1, where the modified diagonal starts with d1′=b1d_1' = b_1 and proceeds as
di′=bi−aici−1′,i=2,…,n. d_i' = b_i - a_i c_{i-1}', \quad i = 2, \dots, n.
The right-hand side is then updated forward as r1′=r1/d1′r_1' = r_1 / d_1' and
ri′=ri−airi−1′di′,i=2,…,n. r_i' = \frac{r_i - a_i r_{i-1}'}{d_i'}, \quad i = 2, \dots, n.
Backward substitution yields the solution xn=rn′x_n = r_n' and xi=ri′−ci′xi+1x_i = r_i' - c_i' x_{i+1} for i=n−1,…,1i = n-1, \dots, 1. This method is a specialized form of Gaussian elimination that exploits the tridiagonal structure to eliminate only adjacent entries, ensuring no fill-in and linear-time execution.[25] For general band matrices with bandwidths pp and qq, LU decomposition adapts Gaussian elimination to perform factorization A=LUA = LU while restricting operations to the band, preventing fill-in outside a slightly widened envelope of bandwidth p+qp+q. The lower triangular factor LL has unit diagonal and lower bandwidth pp, while the upper triangular UU has upper bandwidth qq; elimination proceeds column-by-column, updating only elements within the band using multipliers computed as li,j=ai,j(k)/aj,j(k)l_{i,j} = a_{i,j}^{(k)} / a_{j,j}^{(k)} for i=j+1,…,min⁡(j+p,n)i = j+1, \dots, \min(j+p, n). Solving Ax=bAx = b then involves forward substitution on Ly=bLy = b and back substitution on Ux=yUx = y, both in O(n(p+q))O(n(p+q)) operations, avoiding the O(n3)O(n^3) cost of full Gaussian elimination. This approach is implemented in libraries like LAPACK's routines for banded systems, ensuring numerical stability under diagonal dominance assumptions.[26] Iterative methods, such as the conjugate gradient (CG) algorithm, are effective for symmetric positive definite band matrices, where the bandwidth enables fast matrix-vector products in O(n(p+q))O(n(p+q)) time per iteration, promoting rapid convergence. The CG method generates a sequence of residuals orthogonal with respect to the AA-inner product, minimizing the AA-norm of the error in at most nn steps, but typically converges in far fewer iterations for band matrices due to their clustered eigenvalues and low effective dimension. Preconditioning with a banded incomplete LU factorization further accelerates convergence by approximating the inverse within the band structure, reducing the condition number while maintaining sparsity. For instance, in finite difference discretizations yielding pentadiagonal matrices (p=q=2p = q = 2), CG iterations often number O(κ)O(\sqrt{\kappa}), where κ\kappa is the scaled condition number, yielding overall O(nκ(p+q))O(n \sqrt{\kappa} (p+q)) complexity.[27][28] The development of band matrix solvers traces to the 1940s in numerical analysis, with early contributions including L. H. Thomas's 1949 work on tridiagonal systems and Cornelius Lanczos's 1950 iteration method for tridiagonalizing symmetric matrices via orthogonal transformations, which influenced subsequent direct and iterative solvers by highlighting the utility of banded reductions for eigenvalue and linear problems.[29]

Scientific computing

In scientific computing, band matrices frequently emerge from the discretization of partial differential equations (PDEs) using finite difference methods, which approximate derivatives on structured grids to model physical phenomena such as heat diffusion or fluid flow.[30] For instance, the one-dimensional heat equation, ∂u∂t=α∂2u∂x2\frac{\partial u}{\partial t} = \alpha \frac{\partial^2 u}{\partial x^2}, discretized with central differences in space and implicit time stepping, yields a tridiagonal system matrix where the main diagonal and adjacent subdiagonals capture the local stencil interactions.[31] This structure reflects the sparsity inherent in nearest-neighbor couplings, enabling efficient simulations of diffusion processes in materials or atmospheric models.[32] Extending to higher dimensions, the two-dimensional Poisson equation, −∇2u=f-\nabla^2 u = f, discretized on a uniform n×nn \times n grid using a five-point stencil, results in a block tridiagonal band matrix with tridiagonal blocks, where the overall bandwidth scales as O(n)O(n) due to the row-wise ordering of grid points.[33] This formulation is pivotal in electrostatics simulations and groundwater flow modeling, as the band structure preserves the locality of the differential operator while facilitating scalable computations on large grids.[34] In quantum mechanics, band matrices appear in the Hamiltonian operators of tight-binding models, which approximate electron behavior in periodic solids by considering overlaps between neighboring atomic orbitals.[35] For a one-dimensional lattice, the resulting Hamiltonian is tridiagonal, encoding hopping amplitudes between adjacent sites, and its eigenvalues yield the electronic band structure essential for predicting material properties like conductivity in semiconductors.[36] These models underpin density functional theory extensions and ab initio calculations for nanomaterials.[37] Band matrices also play a key role in signal processing, particularly through Toeplitz structures arising in autoregressive (AR) models that estimate stationary time series from past observations.[38] In AR processes, the covariance matrix is Toeplitz with banded forms when higher-order lags are limited, enabling fast algorithms for linear prediction and filtering tasks such as noise reduction in audio signals or seismic data analysis.[39] This banded Toeplitz property exploits the stationarity assumption to achieve computational efficiency in real-time applications.[38]

Storage and Algorithms

Band storage formats

Band matrices, characterized by their limited bandwidth $ b = p + q + 1 $ where $ p $ is the number of subdiagonals and $ q $ the number of superdiagonals, can be stored efficiently by packing only the nonzero band elements into a compact rectangular array, avoiding the allocation of space for the vast majority of zero entries outside the band.[40] This packed band storage scheme represents the matrix using a two-dimensional array of dimensions $ n \times (p + q + 1) $, where $ n $ is the matrix order, with each column of the array corresponding to a column of the original matrix and rows aligned to capture the diagonals.[40] Specifically, the element $ a_{ij} $ of the band matrix is stored at position $ AB(q + 1 + i - j, j) $ in the storage array $ AB $, for $ i $ ranging from $ \max(1, j - q) $ to $ \min(n, j + p) $, ensuring that the lower and upper parts of the band are shifted appropriately across rows without overlap or gaps in the nonzero structure.[40] This storage requires $ O(n b) $ space complexity, a significant reduction from the $ O(n^2) $ needed for full dense matrix storage, particularly beneficial when $ n $ is large and $ b \ll n $.[40] The memory savings scale linearly with the bandwidth, making it ideal for applications involving wide matrices with narrow bands, such as those arising in finite difference discretizations.[40] In the LAPACK library, this format is standardized under band storage conventions for general band matrices, denoted by routines ending in "GB" (e.g., DGBTRF for LU factorization of a double-precision general band matrix).[40] The leading dimension of the storage array must be at least $ p + q + 1 $, with $ p $ (often denoted $ kl $) specifying the lower bandwidth and $ q $ (denoted $ ku $) the upper bandwidth; unused entries in the corners of the array, outside the band, are not accessed by LAPACK routines and can be arbitrary.[40] For operations like factorization, extra space may be allocated in the upper triangle to accommodate potential fill-in, increasing the effective superdiagonal count to $ p + q $.[40] Compared to full storage, packed band formats offer substantial memory advantages for large-scale problems with small bandwidths, reducing both storage footprint and cache misses in numerical computations while preserving direct access to band elements for efficient algorithm implementation.[40]

Specialized algorithms

Band Cholesky factorization is a specialized decomposition for symmetric positive definite band matrices, where a matrix AA with bandwidth bb is factored as A=LLTA = LL^T with LL lower triangular and also banded with half-bandwidth b/2b/2. This preserves the band structure, limiting update operations during factorization to within the bandwidth, thereby avoiding fill-in outside the band and restricting outer product computations to elements within bb positions of the diagonal. The time complexity is O(nb2)O(n b^2), significantly reducing computation compared to the O(n3)O(n^3) for dense matrices.[41][42] Eigenvalue solvers for band matrices often first reduce the matrix to tridiagonal form using orthogonal transformations like Householder or Givens rotations, followed by iterative methods such as the QR or QL algorithm on the tridiagonal form. For symmetric band matrices, the QR algorithm with shifts computes eigenvalues and eigenvectors while maintaining the band structure, with tridiagonalization requiring O(nb2)O(n b^2) operations and subsequent iterations also scaling as O(nb2)O(n b^2) in the narrow-band limit, versus O(n3)O(n^3) for general dense eigenvalue problems. The QL algorithm serves a similar role for real symmetric tridiagonal matrices, applying left multiplications by QL decompositions to deflate eigenvalues progressively.[43][41] Parallelization of band matrix algorithms frequently employs domain decomposition, partitioning the matrix into overlapping or non-overlapping subdomains to enable concurrent solves on distributed processors. The SPIKE algorithm, a domain decomposition method tailored for banded linear systems, divides the matrix into block-tridiagonal form and solves reduced systems independently on each subdomain, with spike corrections handled via a reduced dense system; this achieves near-linear speedup for large-scale simulations on parallel architectures.[44]

References

  1. Linear Algebra Glossary - UC Davis Math
  2. [PDF] Lecture 4/26/2013 - UC Berkeley math
  3. [PDF] Chapter 4 – Sparse Linear Systems Section 4.2 – Banded Matrices
  4. [PDF] LU Factorization of Banded Matrices - FSU Math
  5. [PDF] Golub and Van Loan - EE IIT Bombay
  6. ALAFF Banded matrices - UT Computer Science
  7. Introduction to Numerical Linear Algebra | Chapter 5: Band matrices
  8. An Algorithm for Reducing the Bandwidth and Profile of a Sparse ...
  9. Comparative Analysis of the Cuthill–McKee and the ... - SIAM.org
  10. [PDF] Better multiplying through structure - Cornell: Computer Science
  11. Diagonally Dominant Matrix -- from Wolfram MathWorld
  12. None
  13. LU decomposition of banded matrices and the solution of linear ...
  14. [PDF] A Comparison of Parallel Solvers for Diagonally Dominant and ...
  15. [PDF] 11.3 Eigenvalues and Eigenvectors of a Tridiagonal Matrix
  16. A fast and stable parallel QR algorithm for symmetric tridiagonal ...
  17. [PDF] 1 Band and skyline solvers - Cornell: Computer Science
  18. Bidiagonal matrix – Knowledge and References - Taylor & Francis
  19. [PDF] Linear Partial Differential Equations, Lec 3 Summary
  20. [PDF] Matrix Computations
  21. [PDF] Improved Finite Difference Formulas for Boundary Value Problems,
  22. [PDF] Matrix structures in queuing models
  23. [PDF] Tridiagonal Matrices: Thomas Algorithm
  24. [PDF] gaussian elimination on a banded matrix
  25. [PDF] Methods of Conjugate Gradients for Solving Linear Systems 1
  26. [PDF] Banded Preconditioning for the Solution of Symmetric ... - DTIC
  27. [PDF] SOME HISTORY OF THE CONJUGATE GRADIENT AND LANCZOS ...
  28. [PDF] FINITE DIFFERENCE AND SPECTRAL METHODS FOR ORDINARY ...
  29. [PDF] Finite difference schemes for the heat equation in one dimension
  30. [PDF] Numerical methods for the heat equation - Daniele Venturi
  31. [PDF] 3.5 Finite Differences and Fast Poisson Solvers
  32. [PDF] Finite Difference Methods For Poisson Equation
  33. [PDF] The Tight Binding Method - Rutgers Physics
  34. Accurate tight-binding Hamiltonian matrices from ab initio calculations
  35. [PDF] 2. Band Structure - DAMTP
  36. [PDF] Toeplitz and Circulant Matrices: A review
  37. [PDF] Design and analysis of Toeplitz preconditioners
  38. Band Storage - The Netlib
  39. https://press.jhu.edu/books/title/10678/matrix-computations
  40. On exact computational complexity of triangular factorization ...
  41. Comparison of eigensolvers for symmetric band matrices
  42. SPIKE: A parallel environment for solving banded linear systems
User Avatar
No comments yet.