Provably Efficient Algorithms for Numerical Tensor Algebra

摘要: Author(s): Solomonik, Edgar | Advisor(s): Demmel, James Abstract: This thesis targets the design of parallelizable algorithms and communication-efficient parallel schedules for numerical linear algebra as well computations with higher-order tensors. Communication is a growing bottleneck in execution most on computers, which manifests itself data movement both through network connecting different processors memory hierarchy each processor synchronization between processors. We provide rigorous theoretical model communication derive lower bounds this model. Our analysis concerns two broad areas tensor contractions. demonstrate practical quality new theoretically-improved by presenting results show that our implementations outperform standard libraries traditional algorithms. costs associated local computation, interprocessor synchronization, to cache transfers schedule based expensive path schedule. introduce technique deriving tradeoffs these apply them dense sparse graph These are attained what we refer 2.5D algorithms, give matrix multiplication, Gaussian elimination, QR factorization, symmetric eigenvalue problem, Floyd-Warshall all-pairs shortest-paths algorithm. achieve bandwidth cost exploiting auxiliary memory. Algorithms employing known have been derived BSP LU alternate versions measurable performance improvements over their counterparts, first evaluations performance. also explore network-topology-aware mapping torus networks multiplication LU, showing how can efficiently exploit collective communication, introducing an adaptation Cannon's algorithm better suited dimension larger than two. For additionally solving challenges memory-bandwidth efficiency arise problem. efficient Krylov subspace methods (repeated vector sparse-matrix), motivated application bound techniques The latter half contains tensors, particular motivating work family coupled-cluster methods, solve many-body Schrodinger equation chemically-accurate electronic structure molecules chemical reactions where electron correlation plays significant role. computation dominated contraction antisymmetric Cyclops Tensor Framework, provides automated mechanism decomposition redistribution data. It leverages perform contractions communication-efficiently. framework capable symmetry antisymmetry tensors utilizes distributed packed-symmetric storage format. Finally, consider theoretically novel number multiplications necessary via computing some redundant terms allow preservation then cancelling out low-order cost. analyze stability adaptations Hermitian matrices. has promising potential accelerating cost, improvement BLAS routines complex