Title  A Parallel Linear Solver for Multilevel Toeplitz Systems with Possibly Several RightHand Sides 
Publication Type  Journal Article 
Year of Publication  2013 
Authors  Chen, J, Li, TLH, Anitescu, M 
Other Numbers  ANL/MCSP50401113 
Abstract  A Toeplitz matrix has constant diagonals; a multilevel Toeplitz matrix is defined recursively with respect to the levels by replacing the matrix elements with Toeplitz blocks. Multilevel Toeplitz linear systems appear in a wide range of applications in science and engineering. This paper discusses an MPI implementation for solving such a linear system by using the conjugate gradient algorithm. The implementation techniques can be generalized to other iterative Krylov methods besides conjugate gradient. These techniques include the use of an arbitrary dimensional process grid for handling the multilevel Toeplitz structure, a communicationhiding approach for performing matrixvector multiplications, the incorporation of multilevel circulant preconditioning for accelerating convergence, an efficient orthogonalization manager for detecting linear dependence in block iterations, and an algorithmic rearrangement to eliminate allreduce synchronizations. The combined use of these techniques leads to a scalable solver for large multilevel Toeplitz systems, possibly with several righthand sides. We show experimental results on matrices of size up to the order of one billion with nearly perfect scaling by using up to 1,024 MPI processes. We also demonstrate an application of the solver in parameter estimation for analyzing largescale climate data.

PDF  http://www.mcs.anl.gov/papers/P50401113.pdf 