zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Parallel Dichotomy Algorithm for solving tridiagonal system of linear equations with multiple right-hand sides. (English) Zbl 1205.68502
Summary: A parallel algorithm for solving a series of matrix equations with a constant tridiagonal matrix and different right-hand sides is proposed and studied. The process of solving the problem is represented in two steps. The first preliminary step is calculating some rows of the inverse matrix of system of linear algebraic equations. The second step consists in calculating solutions for all right-hand sides. For reducing the communication interactions, based on the formulated and proved the main Gaussian Parallel Elimination Theorem for tridiagonal system of equations, we propose an original algorithm for calculating share components of the solution vector. Theoretical estimates validating the efficiency of the approach for both the common- and distributed-memory supercomputers are obtained. Direct and iterative methods of solving a 2D Poisson equation, which include procedures of tridiagonal matrix inversion, are realized using the MPI paradigm. Results of computational experiments on a multicomputer demonstrate a high efficiency and scalability of the parallel Dichotomy Algorithm.
MSC:
68W10Parallel algorithms
Software:
FGb
References:
[1]Samarskii, A. A.: The theory of difference schemes, (2001)
[2]Strikwerda, John C.: Finite difference schemes and partial differential equations, (2004)
[3]Golub, Gene H.; Van Loan, Charles F.: Matrix computations, (1996)
[4]Godunov, S. K.; Ryabenkii, V. S.: Difference schemes: an introduction to the underlying theory, (1984)
[5]Samarskij, A. A.; Nikalayev, E. S.: Numerical methods for grid equations, (1989)
[6]Konovalov, A. N.: Introduction to computational linear algebra methods, (1993)
[7]Morton, K. W.; Mayers, D. F.: Numerical solution of partial differential equations, (2005)
[8]L.H Thomas, Elliptic Problems in Linear Difference Equations Over a Network, Technical report, Watson Sc Comput. Lab. Rept., Columbia University, New York, 1949.
[9]Godunov, S. K.: On numerical solution of systems of ordinary differential equations of first order, Uspekhi mat. Nauk 3, 171-174 (1961)
[10]Horn, Roger A.; Johnson, Charles R.: Matrix analysis, (1990)
[11]Yanenko, N. N.; Konovalov, A. N.; Bugrov, A. N.; Shustov, G. V.: On organizing parallel computing and sweep parallelization, Chislennye metody mekhaniki sploshnoi sredy 9, No. 7, 139-146 (1978)
[12]Gibbs, W. R.: A parallel/recursive algorithm, J. comput. Phys. 201, No. 2, 573-585 (2004) · Zbl 1061.65140 · doi:10.1016/j.jcp.2004.06.008
[13]Sun, Xian-He; Zhang, Hong; Ni, Lionel M.: Efficient tridiagonal solvers on multicomputers, IEEE trans. Comput. 41, No. 3, 286-296 (1992)
[14]Sun, Xian-He; Zhang, Wu: A parallel two-level hybrid method for tridiagonal systems and its application to fast Poisson solvers, IEEE trans. Parallel distrib. Syst. 15, No. 2, 97-106 (2004)
[15]Chawla, M. M.; Passi, K.; Zalik, R. A.: A recursive partitioning algorithm for inverting tridiagonal matrices, Int. J. Comput. math. 37, 213-220 (1990) · Zbl 0724.65021 · doi:10.1080/00207169008803949
[16]Swarztrauber, P. N.: A parallel algorithm for solving general tridiagonal equations, Math. comput. 33, 185-199 (1979) · Zbl 0402.65017 · doi:10.2307/2006035
[17]Stone, Harold S.: Parallel tridiagonal equation solvers, ACM trans. Math. software 1, No. 4, 289-307 (1975) · Zbl 0315.65018 · doi:10.1145/355656.355657
[18]Wakatani, Akiyoshi: A parallel and scalable algorithm for adi method with pre-propagation and message vectorization, Parallel comput. 30, No. 12, 1345-1359 (2004)
[19]Paasonen, V. I.: Boundary conditions of high-order accuracy at the poles of curvilinear systems, Russ. J. Numer. anal. Math. model 14, 369-382 (1999) · Zbl 0941.65087 · doi:10.1515/rnam.1999.14.4.369
[20]Povitsky, Alex: Parallel adi solver based on processor scheduling, Appl. math. Comput. 133, No. 1, 43-81 (2002) · Zbl 1024.65081 · doi:10.1016/S0096-3003(01)00174-6
[21]Dongarra, Jack J.; Duff, Lain S.; Sorensen, Danny C.; Vander Vorst, Henk A.: Numerical linear algebra for high performance computers, (1998)
[22]Heroux, Michael A.; Raghavan, Padma; Simon, Horst D.: Parallel processing for scientific computing (Software, environments and tools), (2006)
[23]V. Malyshkin, V. Korneev, Parallel programming of multicomputers, In Series Textbooks of NSTU, NSTU, 2006.
[24], Sourcebook of parallel computing (2003)
[25]Morse, P.; Feshbach, H.: Methods of theoretical physics, (1999)
[26]Gelfond, A. O.: Calculus of finite differences, (1971)
[27]G. Amdahl, Validity of the single processor approach to achieving large-scale computing capabilities, in: AFIPS Conference Proceedings, vol. 30, 1967, pp. 483 – 485.
[28]R. Rabenseifner, A new optimized mpi reduce algorithm, November 1997. lt;http://www.hlrs.de/mpi/myreduce.htmlgt;.
[29]Janssen, Curtis L.; Nielsen, Ida M. B.: Parallel computing in quantum chemistry, (2008)
[30]Hockney, R. W.; Jesshope, C. R.: Parallel computers two: architecture, programming and algorithms, (1988)
[31]Johnsson, S. Lennart: Solving tridiagonal systems on ensemble architectures, SIAM J. Sci. stat. Comput. 8, No. 3, 354-392 (1987) · Zbl 0624.65021 · doi:10.1137/0908040
[32]Parlett, B. N.: The symmetric eigenvalue problem, (1980) · Zbl 0431.65017
[33]Schlegel, P.: The explicit inverse of a tridiagonal matrix, Math. comput. 24, 665 (1970) · Zbl 0215.55404 · doi:10.2307/2004842
[34]Birkhoff, G.: The numerical solution of elliptic equations, (1972)
[35]Hockney, R. W.: A fast direct solution of Poisson’s equation using Fourier analysis, J. ACM 12, No. 1, 95-113 (1965) · Zbl 0139.10902 · doi:10.1145/321250.321259
[36]Hockney, R. W.; Eastwood, J. W.: Computer simulation using particles, (1988) · Zbl 0662.76002
[37]Peaceman, D. W.; Rachford, H. H.: The numerical solution of parabolic and elliptic differential equations, SIAM j. 3, 28-41 (1955) · Zbl 0067.35801 · doi:10.1137/0103003
[38]Schumann, U.: Fast Fourier transforms for direct solution of Poisson’s equation with staggered boundary conditions, J. comput. Phys. 75, 123-137 (1988) · Zbl 0642.65070 · doi:10.1016/0021-9991(88)90102-7
[39]Cooley, James; Tukey, John: An algorithm for the machine calculation of complex Fourier series, Math. comput. 19, No. 90, 297-301 (1965) · Zbl 0127.09002 · doi:10.2307/2003354
[40]Washspress, E. L.: Optimal alternating-direction-implicate iteration parameters, J. soc. Ind. appl. Math. 10, 339-350 (1962) · Zbl 0111.31401 · doi:10.1137/0110025