Parallel Dense Linear Algebra is the high-performance computing discipline that implements matrix operations (LU, Cholesky, QR factorization, eigenvalue decomposition, SVD) on distributed-memory parallel systems — where the 2D block-cyclic data distribution, BLAS-3 compute kernels, and communication-optimal algorithms enable near-linear scaling to thousands of processors, providing the mathematical foundation for scientific simulation, engineering analysis, and machine learning at supercomputer scale.

Why Dense Linear Algebra Matters

Dense matrix operations appear in: structural analysis (finite element stiffness matrices), quantum chemistry (Hamiltonian eigenvalues), statistics (covariance matrix inversion), control systems (Riccati equations), and deep learning (weight matrix operations). A competitive implementation of dense linear algebra is the starting point for most HPC applications.

2D Block-Cyclic Distribution

The key to parallel efficiency — data must be distributed so that every processor has work throughout the factorization:

• Matrix is divided into blocks of size NB × NB (typically 64-256).
• Blocks are assigned to processors arranged in a P_r × P_c grid using cyclic mapping: block (i,j) goes to processor (i mod P_r, j mod P_c).
• This ensures that as columns are eliminated (LU) or processed (Cholesky), all processors participate at every step — avoiding the idle-processor problem of 1D distribution.

Core Factorizations

LU Factorization (A = PLU):

• Gaussian elimination with partial pivoting. For each column k: find pivot (max element), swap rows, compute multipliers, update trailing submatrix.
• Parallel: panel factorization on one processor column (sequential bottleneck), broadcast pivot/panel, then distributed update of the trailing matrix (BLAS-3 dgemm — the parallel part).
• Performance: N³/(3P) FLOPS per processor for N×N matrix. ScaLAPACK achieves 70-90% of peak FLOPS.

Cholesky Factorization (A = LL^T):

• For symmetric positive-definite matrices. No pivoting needed — more parallelism than LU. N³/(6P) FLOPS per processor.
• Right-looking algorithm: factor diagonal block, solve panel (dtrsm), update trailing matrix (dsyrk + dgemm).
• Communication-optimal Cholesky: 2.5D algorithms reduce communication volume from O(N²/√P) to O(N²/P^(2/3)) by using extra memory for replication.

Libraries and Tools

• ScaLAPACK: The classic distributed dense linear algebra library. MPI + PBLAS (Parallel BLAS) + BLACS (communication layer). Fortran + C interface.
• SLATE: Modern C++ replacement for ScaLAPACK. GPU-accelerated, tile-based algorithms, OpenMP task scheduling. Developed at University of Tennessee.
• cuSOLVER: NVIDIA's GPU-accelerated dense solver library. Single-GPU and multi-GPU LU, Cholesky, QR, eigenvalue, SVD.
• ELPA: Eigenvalue solvers for parallel architectures. Used in materials science (VASP, Quantum ESPRESSO).

Scalability Limits

The panel factorization (sequential per column) creates an Amdahl's Law bottleneck — panel time is O(N²) while update is O(N³). At large P, the panel fraction grows. Mitigation: look-ahead (overlap panel k+1 with update k), communication-avoiding algorithms (CA-LU factors NB columns simultaneously, reducing communication by O(NB)×).

Parallel Dense Linear Algebra is the performance benchmark of scientific computing — the discipline where achieving 90%+ of theoretical peak FLOPS on thousands of processors demonstrates mastery of data distribution, communication optimization, and compute kernel performance.