Fault Oblivious Eigenvalue Solver

Jayanta Mukherjee, Xuejiao Kang, David F. Gleich, Ahmed Sameh, Ananth GramaarXiv 2025 · DOI · arXiv

In the world of high-performance computing (HPC), scale is a double-edged sword. As we move toward exascale systems with hundreds of thousands of cores, hardware failures aren't just a possibility—they are a statistical certainty. When a single node fails during a massive simulation, the traditional "checkpoint-restart" approach forces the entire system to roll back to a previous state, wasting precious time and energy.

A new paper by Jayanta Mukherjee and colleagues from Purdue and Meta proposes a more resilient way forward: the Fault-Oblivious Eigenvalue Solver. Instead of stopping to fix a hole, their algorithm is designed to compute through the failure using the mathematical equivalent of a spare tire.

The Challenge of Fail-Stop Errors

Eigenvalue problems ($Ax = \lambda x$) are the backbone of everything from structural engineering simulations to machine learning. On massive parallel platforms, these computations are often interrupted by "fail-stop" errors—where a processor simply dies and its data vanishes.

Current solutions are often inefficient:

  1. Checkpoint-Restart: Periodically saving the state to disk. If a fault occurs, you reload and try again. This creates massive I/O bottlenecks.
  2. Active Replication: Running the same math on multiple processors. This is reliable but doubles or triples the hardware cost.

The authors sought a "middle way" through Algorithm-Based Fault Tolerance (ABFT). They wanted a solver that could lose a chunk of its matrix and still produce the correct answer without starting over.

Methods: Erasure Coding for Linear Algebra

The core innovation is the application of erasure coding—a technique usually reserved for data storage (like RAID)—to active linear algebra.

Problem Reformulation

The authors augment the original matrix $A$ with a coding matrix $E$. By doing this, they transform the standard problem into a Generalized Eigenvalue Problem (GEP): $\tilde{A}\tilde{x} = \lambda \tilde{B}\tilde{x}$.

The "Oblivious" Recovery

When a fault occurs (e.g., a row or column of $A$ is lost), the algorithm doesn't panic. It uses pre-computed redundant blocks ($R=AE, S=E^T AE, T=E^T E$) to "patch" the missing parts of the system.

Schematic of the matrix augmentation and recovery process using erasure coding.

As shown in the figure above, the augmented matrix $\tilde{A}$ contains the original matrix $A$ along with redundant blocks $AE$, $E^T A$, and $E^T AE$. When $k$ rows and columns are erased, the system can be reconstituted using these blocks to form a new system $A'$ that maintains the spectral properties of the original.

TraceMin Integration

While they demonstrate the technique on the Power Method, the star of the paper is its implementation in TraceMin, a robust and scalable eigensolver. They show that the "reconstituted" system maintains the same eigenvalues as the original, allowing the solver to continue converging even after a crash.

Experimental Evaluation

The authors evaluated their solver on a diverse set of benchmarks to ensure it works for both dense and sparse data:

  • Dense Matrices: Covariance matrices derived from the MNIST (handwritten digits) and CIFAR-10 (image classification) datasets.
  • Sparse Matrices: Eight different matrices from the SuiteSparse Matrix Collection, including bcsstk17 (stiffness matrix), gyro (model reduction), and torsion1 (optimization).

Key Insights

  • Mathematical Equivalence: The authors proved that the augmented, potentially singular system still contains the exact eigenvalues of the original problem. The "extra" eigenvalues created by the augmentation are easily detectable and can be discarded.
  • Symmetry Preservation: Unlike previous attempts to solve linear systems with erasure coding, this method carefully maintains the symmetry of the matrices, which is vital for the stability of eigensolvers like TraceMin.
  • Randomized Recovery: When a fault occurs, the lost parts of the eigenvector are replaced with random data. Surprisingly, the solver’s natural convergence properties quickly pull this random noise back into the correct subspace.

Results and Performance

  • Minimal Overhead: In single-fault scenarios, the erasure-coded TraceMin took less than 20% additional iterations to converge compared to a fault-free run.
  • Scalability: The solver demonstrated robust convergence even in "Multifault" scenarios where multiple nodes failed at different times.
  • Efficiency: The timing breakdown showed that the time spent generating the coding blocks and "reconstituting" the matrix was negligible compared to the total solver time.

Limitations and Future Work

The current model primarily handles "erasure" (data loss) rather than "soft faults" (bit-flips). Additionally, while much cheaper than replication, adding redundant rows and columns does increase the memory footprint. Future research may explore more complex coding schemes and apply this "fault-oblivious" philosophy to other types of iterative solvers.

Summary updated

Abstract

Eigenvalue problems serve as fundamental substrates for applications in large-scale scientific simulations and machine learning, often requiring computation on massively parallel platforms. As these platforms scale to hundreds of thousands of cores, hardware failures become a significant challenge to reliability and efficiency. In this paper, we propose and analyze a novel fault-tolerant eigenvalue solver based on erasure-coded computations -- a technique that enhances resilience by augmenting the system with redundant data a priori. This transformation reformulates the original eigenvalue problem as a generalized eigenvalue problem, enabling fault-oblivious computation while preserving numerical stability and convergence properties. We formulate the augmentation scheme, establish the necessary conditions for the encoded blocks, and prove the relationship between the original and transformed problems. We implement an erasure-coded TraceMin eigensolver and demonstrate its effectiveness in extracting eigenvalues in the presence of faults. Our experimental results show that the proposed solver incurs minimal computational overhead, maintains robust convergence, and scales efficiently with the number of faults, making it a practical solution for resilient eigenvalue computations in large-scale systems.
BibTeX
@misc{mukherjee2025fault,
  author = {Jayanta Mukherjee and Xuejiao Kang and David F. Gleich and Ahmed Sameh and Ananth Grama},
  title = {{Fault Oblivious Eigenvalue Solver}},
  year = {2025},
  eprint = {2511.13396},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.13396},
}

Loading related content...

Figure