Optimal and efficient parallel tridiagonal solvers using direct methods

DOI10.1023/B:SUPE.0000040615.60545.C6MaRDI QIDQ2386702zbMATH OpenOpenAlexFDO

Authors Eunice E. Santos

Publication date 25 August 2005

Published in The Journal of Supercomputing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/b:supe.0000040615.60545.c6

zbMATH Keywords

\(\log P\) modeldirect methodsodd-even cyclic reductionparallel algorithmsprefix summingtridiagonal linear systems

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20)

Review text

The problem of solving tridiagonal linear systems on parallel distributed-memory environments is considered. The derivation of lower bounds on running time, and the design and analysis of algorithms is discussed for a wide-range of machines, networks, and clusters. The primary focus is on two direct methods: odd-even cyclic reduction, and prefix summing. The author determines the types of layouts and communication patterns that are needed to achieve efficient and/or optimal running times for a particular direct method. He presents a variety of lower bounds based on assumptions on data layouts. He presents algorithms that are asymptotically optimal to the lower bounds, and gives comparative results for two chosen direct methods.

Recommendations

• scientific article; zbMATH DE number 1760070
• Parallel Factorizations for Tridiagonal Matrices
• A parallel algorithm for solving tridiagonal linear systems
• scientific article; zbMATH DE number 1302611
• Optimized cyclic reduction for the solution of linear tridiagonal systems on parallel computers

Cited in

(11)

• On optimal message vector length for block single parallel partition algorithm in a three-dimensional ADI solver
• Optimizing Tridiagonal Solvers for Alternating Direction Methods on Boolean Cube Multiprocessors
• Revisiting parallel cyclic reduction and parallel prefix-based algorithms for block tridiagonal systems of equations
• Optimal Bounds for Solving Tridiagonal Systems with Preconditioning
• scientific article; zbMATH DE number 1302611 (Why is no real title available?)
• scientific article; zbMATH DE number 1760070 (Why is no real title available?)
• scientific article; zbMATH DE number 1877172 (Why is no real title available?)
• A direct incomplete factorization method for parallel solution of tridiagonal linear systems
• Manycore algorithms for batch scalar and block tridiagonal solvers
• Generalized scans and tridiagonal systems
• A cost-optimal parallel tridiagonal system solver

This page was built for publication: Optimal and efficient parallel tridiagonal solvers using direct methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2386702)