Block pivoting implementation of a symmetric Toeplitz solver

• Published in: Journal of parallel and distributed computing 2014-05, Vol.74 (5), p.2392-2399
• Main Authors: Alonso, Pedro, Dolz, Manuel F., Vidal, Antonio M.
• Format: Article
• Language: English
• Subjects: Algebra; Displacement structure; Exact sciences and technology; Linear and multilinear algebra, matrix theory; Linear systems; Mathematics; Multicores; Pivoting; Sciences and techniques of general use; Symmetric Toeplitz matrices
• ISSN: 0743-7315; 1096-0848
• DOI: 10.1016/j.jpdc.2014.02.003

Toeplitz matrices are characterized by a special structure that can be exploited in order to obtain fast linear system solvers. These solvers are difficult to parallelize due to their low computational cost and their closely coupled data operations. We propose to transform the Toeplitz system matrix into a Cauchy-like matrix since the latter can be divided into two independent matrices of half the size of the system matrix and each one of these smaller arising matrices can be factorized efficiently in multicore computers. We use OpenMP and store data in memory by blocks in consecutive positions yielding a simple and efficient algorithm. In addition, by exploiting the fact that diagonal pivoting does not destroy the special structure of Cauchy-like matrices, we introduce a local diagonal pivoting technique which improves the accuracy of the solution and the stability of the algorithm. •We improve the solution of symmetric Toeplitz linear systems in multicore systems.•We transform the Toeplitz matrix into a Cauchy-like one to obtain some benefits.•The problem is partitioned into two half-sized independent problems.•We use partial local pivoting to improve the accuracy of the solution.•We propose a special scheme to store data in memory that accelerates the algorithm.