Efficient Numerical Methods for Large-Scale Sparse Linear Systems

Thesis Abstract

This study addresses the challenge of solving large-scale sparse linear systems efficiently, a problem central to simulations in scientific computing, engineering, and data-driven modeling where system matrices arise from discretizations of partial differential equations and graph-based problems. The aim is to design, implement, and evaluate numerical methods that achieve robust convergence, reduced memory footprint, and scalable performance on contemporary high-performance computing architectures. The specific objectives are (1) to develop and hybridize iterative solvers (e.g., GMRES, BiCGSTAB, and multigrid variants) with conditioning-aware preconditioners; (2) to investigate matrix-free techniques and inexact Krylov subspace strategies to lower per-iteration costs; (3) to implement parallel and accelerators-enabled algorithms exploiting vectorization and GPU offloading; (4) to assess robustness across representative sparse matrix families arising from structural mechanics, reservoir simulation, and graph Laplacians; (5) to benchmark against established libraries and datasets to quantify improvements in time-to-solution and memory consumption; and (6) to formalize guidelines for method selection given matrix properties and hardware constraints. The methodology adopts a design, implement, and evaluate research framework. A cross-domain corpus of 1,000 sparse matrices will be sourced from the SuiteSparse Matrix Collection, the U.S. Department of Energy repositories, and synthetic benchmarks to cover a spectrum of sparsity patterns, condition numbers, and spectral properties. An experimental software stack will be developed in C++ and CUDA, integrating existing libraries (PETSc, Trilinos, cuSPARSE) with novel preconditioners and multilevel strategies. The population comprises computational linear systems generated from discretized partial differential equations and network-based graph problems; a stratified sample of 300 matrices will be selected to ensure representation of ill-conditioned cases and highly irregular sparsity. Data collection will record metrics including convergence rate, iteration count, time-to-solution, memory footprint, and scalability across 16, 32, 64, and 128 GPU/CPU cores. Validity and reliability will be ensured through unit tests, regression tests, and reproducibility checks across three independent computing platforms a CPU-only cluster, a GPU-accelerated workstation, and a heterogeneous supercomputer. Analytical methods will combine quantitative performance analysis with statistical inference. Descriptive statistics will summarize solver behavior, while inferential analyses will compare methods using repeated-measures ANOVA and pairwise non-parametric tests where assumptions fail. Regression analysis will model time-to-solution as a function of matrix properties (size, sparsity pattern, condition number) and hardware configuration. A multi-criteria decision analysis framework will be used to synthesize trade-offs between convergence robustness, memory usage, and computational throughput. The study will also apply spectral analysis to understand preconditioner impact on eigenvalue distribution and convergence. The theoretical component will draw upon established theories of Krylov subspace methods, multigrid theory (two- and three-grid cycles), and matrix-free iteration concepts, referencing relevant results from Saad (Iterative Methods for Sparse Linear Systems) and Trottenberg et al. The analytical framework will be complemented by a finite-element test case representing elasticity problems and a reservoir-modeling scenario to demonstrate applicability in engineering simulations. Expected findings include that hybrid multigrid-preconditioned Krylov solvers with matrix-free right-preconditioning achieve substantial reductions in iteration counts (up to 55%) and memory usage (up to 40%) for ill-conditioned systems, particularly those with anisotropic discretizations. GPU-accelerated implementations are anticipated to deliver near-linear scalability up to 128 GPUs for structured sparsity, while unstructured patterns will exhibit diminishing returns beyond 64 compute units unless communication-avoiding variants are employed. The study will provide a taxonomy of solver choices mapped to matrix characteristics and hardware profiles, along with a validated benchmark suite and a reproducible software framework. Contributions to knowledge include (1) a generalized, architecture-aware methodology for selecting and configuring efficient large-scale sparse solvers; (2) novel preconditioning strategies tailored to matrix-free and multilevel contexts; and (3) an open-source, extensible solver platform compatible with major numerical linear algebra libraries. The principal conclusion is that a coordinated integration of matrix-free inexact Krylov methods with block-structured multigrid and communication-avoiding techniques yields consistent performance gains across diverse sparse systems and hardware environments. Recommendations emphasize adaptive solver selection guided by spectral diagnostics, dynamic preconditioner tuning for heterogeneous architectures, and continued development of reproducible benchmarks to standardize performance evaluations in large-scale sparse linear system applications.