Dense Patch-oriented Matrix Factorization on a Hypercube Multiprocessor

We develop algorithms for Cholesky factorization and the solution of triangular systems of linear equations on a hypercube multiprocessor. Specifically, we describe algorithms that apply when the matrix is distributed around the hypercube by submatrices, or patches. We show that these algorithms use asymptomatically less internode communication than more common row- and column- oriented algorithms. Empirical results accompany the analysis and show that patch-oriented algorithms are competitive with, but not demonstrably superior to, the other algorithms for hypercubes of low dimension. Implementations in C appear in an appendix