In modern distributed computing, the performance of numerical linear algebra is rarely limited by raw floating-point operations (FLOPs). Instead, it hits a "communication wall." Traditional algorithms for solving linear systems, computing QR decompositions, or performing orthogonalization are inherently sequential. For instance, standard forward or backward substitution requires solving for one variable before moving to the next, forcing parallel processors to constantly wait for updates from their neighbors. This frequent global synchronization destroys parallel scalability on large clusters and multi-GPU architectures.
To overcome this bottleneck, a powerful paradigm has emerged: breaking sequential dependencies by restructuring algorithms around local block operations and selective inversion. By performing slightly more local computation—such as explicitly inverting small diagonal blocks or computing randomized sketches—these methods transform communication-heavy, sequential dependencies into highly parallel matrix-vector or matrix-matrix multiplications.
Transforming Sequential Solves via Block Inversion and Tearing
Consider a triangular linear system $Lx = b$. The standard way to solve this is through successive substitution, which is a strictly sequential process. If $L$ is distributed across multiple processors, each processor must wait for the preceding processor to finish computing its component of $x$ before it can begin its own work.
Tobias Wicky et al. in Communication-Avoiding Parallel Algorithms for Solving Triangular Systems of Linear Equations demonstrate how to bypass this bottleneck using selective inversion. Instead of performing sequential substitution, the algorithm partitions the triangular matrix into diagonal blocks and explicitly inverts these blocks in parallel. Because triangular inversion is uniquely stable compared to general matrix inversion, this step preserves numerical accuracy. Once the diagonal blocks are inverted, the sequential substitution steps are transformed into independent matrix-matrix multiplications, which can be executed with high efficiency using optimized parallel kernels.
Traditional Substitution (Sequential):
[ L11 0 0 ] [ x1 ] [ b1 ] --> Solve L11*x1 = b1
[ L21 L22 0 ] [ x2 ] = [ b2 ] --> Wait for x1, then solve L22*x2 = b2 - L21*x1
[ L31 L32 L33] [ x3 ] [ b3 ] --> Wait for x2, then solve L33*x3 = b3 - L31*x1 - L32*x2
Selective Inversion (Parallel):
1. Invert diagonal blocks locally: Compute L11⁻¹, L22⁻¹, L33⁻¹
2. Transform into parallel matrix multiplications:
x1 = L11⁻¹ * b1
x2 = L22⁻¹ * (b2 - L21*x1) -- (Inter-block updates use parallel GEMM)
A similar intuition applies to banded and tridiagonal systems. Ahmed Sameh introduced a "tearing" strategy in A tearing-based hybrid parallel banded linear system solver, which decomposes a banded system into overlapping independent blocks. The processors solve these local subproblems concurrently and then synchronize via a minimal, reduced "balance" system.
For fractional reaction-diffusion equations, Chunye Gong et al. leverage a divide-and-conquer strategy in An efficient parallel algorithm for Caputo fractional reaction-diffusion equation with implicit finite-difference method to partition large tridiagonal matrices, generating a reduced system that requires only minimal boundary data exchange.
By shifting the computational burden from global synchronization to local matrix manipulation, these methods allow complex solvers—such as the parallel sweeping preconditioners for 3D Helmholtz equations developed by Jack Poulson et al. in A Parallel Sweeping Preconditioner for Heterogeneous 3D Helmholtz Equations—to scale effectively across massive distributed clusters.
Low-Synchronization Orthogonalization and Pivoting
The communication bottleneck is equally severe in orthogonalization processes, such as the Gram-Schmidt method used within QR factorizations or Anderson Acceleration (AA) for nonlinear solvers. Standard Modified Gram-Schmidt (MGS) requires a global synchronization step for every single vector to compute dot products, creating a quadratic dependency on the number of vectors.
To break this dependency, researchers group vectors into blocks and use compact mathematical representations to aggregate communication. Yusaku Yamamoto in A parallel algorithm for incremental orthogonalization based on the compact WY representation shows that leveraging the compact WY representation of Householder transformations allows vector-vector operations to be recast as matrix-vector multiplications. This reduces the frequency of interprocessor synchronizations from a quadratic scale down to a linear scale.
Taking this further, Shelby Lockhart et al. studied low-synchronization methods like Inverse Compact WY (ICWY-MGS) in Performance of Low Synchronization Orthogonalization Methods in Anderson Accelerated Fixed Point Solvers. They demonstrate that grouping dot products can reduce global reductions to a constant two synchronizations per iteration, completely independent of the history size $m$.
Similarly, the Randomized Block Gram-Schmidt (RBGS) process designed by Oleg Balabanov et al. in Randomized Block Gram-Schmidt Process for the Solution of Linear Systems and Eigenvalue Problems achieves a low-synchronization profile by requiring only a single global synchronization per block.
This block-wise reduction strategy also extends to matrix pivoting and factorization. In LU Factorization with Panel Rank Revealing Pivoting and Its Communication Avoiding Version, Amal Khabou et al. introduce hierarchical tournament pivoting. Instead of searching for pivots row-by-row (which requires frequent communication), they partition the matrix into blocks and use a reduction tree to select pivots for an entire block of columns simultaneously.
Traditional MGS:
Vector 1 ---> [Global Sync: Dot Product] ---> Orthogonalize Remaining
Vector 2 ---> [Global Sync: Dot Product] ---> Orthogonalize Remaining
Vector 3 ---> [Global Sync: Dot Product] ---> Orthogonalize Remaining
(Total Syncs = O(m))
Low-Synchronization Block GS:
[ Vector Block (1, 2, 3) ] ---> [Single Global Sync for Block] ---> Parallel Matrix Update
(Total Syncs = O(1) per block)
Trading Redundant Computation for Communication Efficiency
Why do these strategies work so well on modern hardware? The fundamental principle relies on a deliberate trade-off: local computation and memory redundancy are significantly cheaper than network latency.
For example, in Space-Round Tradeoffs for MapReduce Computations, Andrea Pietracaprina et al. formalize this trade-off by showing how data replication across nodes can drastically reduce the number of communication rounds needed for matrix operations. In the context of tall matrices (matrices with far more rows than columns), Maksim Melnichenko et al. combine randomized sketching with a preconditioned CholeskyQR approach in CholeskyQR with Randomization and Pivoting for Tall Matrices (CQRRPT) to minimize global data transfers.
By structuring algorithms so that processors work on independent, well-conditioned blocks—whether through row paving in constrained systems (Deanna Needell et al. in Block Kaczmarz Method with Inequalities) or structured orthogonal factorizations in boundary value problems (Stephen Wright in Stable Parallel Algorithms for Two-Point Boundary Value Problems)—the need for constant global coordination is eliminated.
Ultimately, selective inversion and low-synchronization block methods shift the paradigm of parallel linear algebra. They replace fine-grained, step-by-step dependencies with coarse-grained, highly concurrent matrix operations, allowing numerical solvers to break through the communication wall.
Key Foundational Work
A tearing-based hybrid parallel banded linear system solver (2008) — contributed 2 concept elements to this direction.
Stable Parallel Algorithms for Two-Point Boundary Value Problems (1992) — contributed 1 concept elements to this direction.