Questions on the theory of distributed numerical algebraic computation

Question

I'm trying to build a pure python distributed numerical algebra computation kernel based on GPU. but after I've learnt most of the software engineering, I realise that I'm seriously lacking in computational theory. Does anyone have any recommendations for books or materials? So far I have implemented a distributed matrix multiplication, and I know that I may have to write block based matrix transpose, matrix equation solving (LU,QR), eigenvalues, matrix factorisation, non-linear least squares. Any other knowledge or paper recommendations?

Answer 1

Building such a library from scratch is a serious undertaking. The SLATE library, which targets the functionality you're looking at, has taken about 6 years with 4-7 full-time developers, most of them having Ph.D.s in numerical computing and experience with LAPACK, ScaLAPACK, MAGMA, PLASMA, etc. And there's still some missing functionality (e.g., a non-symmetric eigen-solver). So, if your goal is working software within the next year or two, you'll want to use an existing library. SLATE and DPLASMA are the options I know of that cover your desired functionality (although, I'm unaware of Python bindings for either). I work on SLATE, and DPLASMA is developed in the same group. So, feel free to reach out.

If your goal is more educational, the literature mostly exists as research papers with an occasional survey paper. But, there's a lot of engineering work that doesn't make it into publications, so I'd still recommend spending some time playing with or contributing to an existing code. Doing a Ph.D. is the traditional way to learn a lot of this material.

For a general idea of the development of this type of library and basic techniques, you could look at the ScaLAPACK user guide and the SLATE working notes and publications. (There might be some retrospectives of ScaLAPACK out there, too.) MAGMA's publications and the LAPACK working notes mostly consider single-node systems, but have a lot of good material.

For matrix multiplication, I think "Red-Blue Pebbling Revisited: Near Optimal Parallel Matrix-Matrix Multiplication" by Kwasniewski et al. is the state of the art and discusses previous works. But, even the 2.5D algorithm can achieve a decent percent of the theoretical peak.

For LU, tournament pivoting ("CALU: a communication optimal LU factorization algorithm" by Grigori and Demmel) or threshold pivoting ("Threshold Pivoting for Dense LU Factorization" by myself) do better than traditional partial pivoting. "A survey of recent developments in parallel implementations of Gaussian elimination" by Donfack et al. and my dissertation provides a discussion on a few other approaches too. "A survey of recent developments in parallel implementations of Gaussian elimination" by Kurzak et al. provides a high-level outline of SLATE's LU and Cholesky.

For QR, you'll probably want to look at CAQR from "Communication-optimal parallel and sequential QR and LU factorizations" by Demmel et al.

For SVD and hermitian eigenvalue problems, "The Singular Value Decomposition: Anatomy of Optimizing an Algorithm for Extreme Scale" by Dongarra et al. is a fairly robust survey.