Communication requirements of sparse Cholesky factorization with nested dissection orderingLoad distribution schemes for minimizing the communication requirements of the Cholesky factorization of dense and sparse, symmetric, positive definite matrices on multiprocessor systems are presented. The total data traffic in factoring an n x n sparse symmetric positive definite matrix representing an n-vertex regular two-dimensional grid graph using n exp alpha, alpha not greater than 1, processors are shown to be O(n exp 1 + alpha/2). It is O(n), when n exp alpha, alpha not smaller than 1, processors are used. Under the conditions of uniform load distribution, these results are shown to be asymptotically optimal.
Document ID
19890064856
Acquisition Source
Legacy CDMS
Document Type
Conference Paper
Authors
Naik, Vijay K. (NASA Langley Research Center Hampton, VA, United States)
Patrick, Merrell L. (Duke University Durham, NC, United States)
Date Acquired
August 14, 2013
Publication Date
January 1, 1989
Subject Category
Computer Systems
Meeting Information
Meeting: SIAM Conference on Parrallel Processing for Scientific Computing
Location: Los Angeles, CA
Country: United States
Start Date: December 1, 1987
End Date: December 4, 1987
Sponsors: Society for Industrial and Applied Mathemetics