Back to search

Georgia Institute of Technology

New Parallel Algorithms for Large-Scale Matrix Computations

Abstract

dc:description.abstract

Matrix computation is a critical part of scientific simulations and data analysis in fields such as density functional theory, recommendation systems, and neural networks. With the exponential growth in dataset sizes and computational problems, it is imperative to develop scalable parallel algorithms for efficient dense and sparse matrix operations. This dissertation presents innovative scale-out algorithms that leverage multiple processors to simultaneously and addressing data movement bottlenecks, and scale-up algorithms focus on single-node performance by exploiting matrix properties like sparsity and low-rank structures. In this dissertation, we first propose the communication-avoiding 3D matrix multiplication algorithm (CA3DMM). CA3DMM is an approach to parallelize general dense matrix multiplication that minimizes communication sizes by optimizing matrix partitioning and data transfer patterns. CA3DMM achieves the theoretical communication cost lower bound with a simple formation and shows superior parallel performance compared to existing methods. We then propose a hybrid approach for efficient distributed-memory polar decomposition (PD) calculation, which can be used for computing eigenvalue decomposition and singular value decomposition. The proposed hybrid PD approach combines multiple iterative methods for computing PD and utilizes CA3DMM and a new parallel orthonormalization algorithm for better performance. For large sparse matrices, we propose the communication-reduced parallel sparse-dense matrix multiplication (CRP-SpMM) algorithm. This algorithm can benefit from existing sparse matrix partitioning methods for sparse matrix-dense vector multiplication (SpMV), and further explores more effective 2D process grid sizes to reduce communication costs by parallelizing the computation of different columns of the dense input matrix. The parallel implementation of CRP-SpMM significantly outperforms existing distributed-memory parallel SpMM codes. Lastly, we present the design and parallel implementation of H2Pack, a high-performance multi-purpose library for kernel matrices. Combining multiple state-of-the-art mathematical methods, H2Pack can compress kernel matrices using the H^2 matrix format, resulting in O(N) storage and matrix-vector multiplication costs. As a result, H2Pack can easily and efficiently handle million-by-million kernel matrices on personal computers, while outperforming the widely used fast multipole method (FMM) on multiple tasks.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computational Science and Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Huang, Hua
Advisor dc:contributor.advisor
  • Chow, Edmond
Committee members dc:contributor.committeemember
  • Xi, Yuanzhe
  • Suryanarayana, Phanish
  • Catalyurek, Umit
  • Xu, Helen

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/75672

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Huang, Hua. New Parallel Algorithms for Large-Scale Matrix Computations. Doctoral thesis, Georgia Institute of Technology, 2024. https://hdl.handle.net/1853/75672