Parallelism in Matrix Computations (Scientific Computation)

This book is primarily intended as a research monograph that could also be used in graduate courses for the design of parallel algorithms in matrix computations.

It assumes general but not extensive knowledge of numerical linear algebra, parallel architectures, and parallel programming paradigms.

The book consists of four parts: (I) Basics; (II) Dense and Special Matrix Computations; (III) Sparse Matrix Computations; and (IV) Matrix functions and characteristics. Part I deals with parallel programming paradigms and fundamental kernels, including reordering schemes for sparse matrices. Part II is devoted to dense matrix computations such as parallel algorithms for solving linear systems, linear least squares, the symmetric algebraic eigenvalue problem, and the singular-value decomposition. It also deals with the development of parallel algorithms for special linear systems such as banded ,Vandermonde ,Toeplitz ,and block Toeplitz systems. Part III addresses sparse matrix computations: (a) the development of parallel iterative linear system solvers with emphasis on scalable preconditioners, (b) parallel schemes for obtaining a few of the extreme eigenpairs or those contained in a given interval in the spectrum of a standard or generalized symmetric eigenvalue problem, and (c) parallel methods for computing a few of the extreme singular triplets. Part IV focuses on the development of parallel algorithms for matrix functions and special characteristics such as the matrix pseudospectrum and the determinant. The book also reviews the theoretical and practical background necessary when designing these algorithms and includes an extensive bibliography that will be useful to researchers and students alike.

The book brings together many existing algorithms for the fundamental matrix computations that have a proven track record of efficient implementation in terms of data locality and data transfer on state-of-the-art systems, as well as several algorithms that are presented for the first time, focusing on the opportunities for parallelism and algorithm robustness.

這本書主要是一本研究專著，也可用於矩陣計算中並行算法的研究生課程。它假設讀者對數值線性代數、並行架構和並行編程範式有一般但不深入的了解。

該書分為四個部分：(I) 基礎知識；(II) 密集和特殊矩陣計算；(III) 稀疏矩陣計算；和 (IV) 矩陣函數和特性。第一部分介紹了並行編程範式和基本核心算法，包括稀疏矩陣的重排序方案。第二部分專注於密集矩陣計算，如解線性系統的並行算法、線性最小二乘問題、對稱代數特徵值問題和奇異值分解。它還處理了特殊線性系統（如帶狀、范德蒙德、托普利茨和塊托普利茨系統）的並行算法開發。第三部分討論稀疏矩陣計算：(a) 開發並行迭代線性系統求解器，重點是可擴展的預條件器；(b) 用於在標準或廣義對稱特徵值問題的頻譜中獲取少數極值特徵對或特定區間內的並行方案；(c) 用於計算少數極值奇異三元組的並行方法。第四部分專注於矩陣函數和特性的並行算法開發，如矩陣虛譜和行列式。該書還回顧了設計這些算法所需的理論和實踐背景，並包含了對研究人員和學生都有用的廣泛參考文獻。

該書匯集了許多現有的基本矩陣計算算法，這些算法在最先進的系統上以數據局部性和數據傳輸的效率方面都有有效實現的經驗。同時，該書還介紹了一些首次提出的算法，重點放在並行性和算法的穩健性上。