The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Dalam makalah ini kami membandingkan pelbagai prasyarat selari seperti Point-SSOR (Symmetric Successive OverRelaxation), ILU(0) (LU Tidak Lengkap) dalam susunan Wavefront, ILU(0) dalam susunan Multi-color, Multi-Color Block SOR (Successive OverRelaxation), SPAI (Sparse Approximate Inverse) dan pARMS (Parallel Algebraic Recursive Multilevel Solver) untuk menyelesaikan sistem linear jarang besar yang timbul daripada PDE (Persamaan Pembezaan Separa) dua dimensi pada grid berstruktur. Point-SSOR terkenal, dan ILU(0) ialah salah satu prasyarat yang paling popular, tetapi ia sememangnya siri. ILU(0) dalam susunan Wavefront memaksimumkan keselarian dalam susunan semula jadi, tetapi panjang muka gelombang selalunya tidak seragam. ILU(0) dalam susunan berbilang warna ialah cara mudah untuk mencapai persamaan susunan N, Di mana N ialah susunan matriks, tetapi kadar penumpuannya sering merosot berbanding dengan susunan semula jadi. Kami telah memilih prasyarat SOR Blok Berbilang Warna yang digabungkan dengan penyelesai matriks jarang langsung, kerana untuk matriks Laplacian kaedah SOR diketahui mempunyai kadar penumpuan yang tidak merosot apabila digunakan dengan pesanan Berbilang Warna. Dengan menggunakan versi blok kami mengharapkan untuk meminimumkan komunikasi antara pemproses. SPAI mengira songsang anggaran jarang secara langsung dengan kaedah kuasa dua terkecil. Akhir sekali, ARMS ialah prasyarat yang secara rekursif mengeksploitasi konsep set bebas dan pARMS ialah versi selari ARMS. Eksperimen telah dijalankan untuk pendiskretan Perbezaan Terhad dan Elemen Terhingga bagi lima PDE dua dimensi dengan saiz jejaring besar sehingga satu juta pada mesin IBM p595 dengan memori teragih. Matriks kami ialah positif sebenar, iaitu bahagian sebenar nilai eigen adalah positif. Kami telah menggunakan GMRES(m) sebagai kaedah lelaran luar kami, supaya penumpuan GMRES(m) untuk matriks ujian kami dijamin secara matematik. Komunikasi antara pemproses dilakukan menggunakan primitif MPI (Message Passing Interface). Keputusan menunjukkan bahawa secara amnya ILU(0) dalam susunan Pelbagai Warna dan ILU(0) dalam susunan Wavefront mengatasi kaedah lain tetapi untuk matriks 5 mata simetri dan hampir simetri SOR Blok Berbilang Warna memberikan prestasi terbaik, kecuali untuk beberapa kes dengan bilangan pemproses yang kecil.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Sangback MA, "A Performance Comparison of the Parallel Preconditioners for Iterative Methods for Large Sparse Linear Systems Arising from Partial Differential Equations on Structured Grids" in IEICE TRANSACTIONS on Fundamentals,
vol. E91-A, no. 9, pp. 2578-2587, September 2008, doi: 10.1093/ietfec/e91-a.9.2578.
Abstract: In this paper we compare various parallel preconditioners such as Point-SSOR (Symmetric Successive OverRelaxation), ILU(0) (Incomplete LU) in the Wavefront ordering, ILU(0) in the Multi-color ordering, Multi-Color Block SOR (Successive OverRelaxation), SPAI (SParse Approximate Inverse) and pARMS (Parallel Algebraic Recursive Multilevel Solver) for solving large sparse linear systems arising from two-dimensional PDE (Partial Differential Equation)s on structured grids. Point-SSOR is well-known, and ILU(0) is one of the most popular preconditioner, but it is inherently serial. ILU(0) in the Wavefront ordering maximizes the parallelism in the natural order, but the lengths of the wavefronts are often nonuniform. ILU(0) in the Multi-color ordering is a simple way of achieving a parallelism of the order N, where N is the order of the matrix, but its convergence rate often deteriorates as compared to that of natural ordering. We have chosen the Multi-Color Block SOR preconditioner combined with direct sparse matrix solver, since for the Laplacian matrix the SOR method is known to have a nondeteriorating rate of convergence when used with the Multi-Color ordering. By using block version we expect to minimize the interprocessor communications. SPAI computes the sparse approximate inverse directly by least squares method. Finally, ARMS is a preconditioner recursively exploiting the concept of independent sets and pARMS is the parallel version of ARMS. Experiments were conducted for the Finite Difference and Finite Element discretizations of five two-dimensional PDEs with large meshsizes up to a million on an IBM p595 machine with distributed memory. Our matrices are real positive, i.e., their real parts of the eigenvalues are positive. We have used GMRES(m) as our outer iterative method, so that the convergence of GMRES(m) for our test matrices are mathematically guaranteed. Interprocessor communications were done using MPI (Message Passing Interface) primitives. The results show that in general ILU(0) in the Multi-Color ordering and ILU(0) in the Wavefront ordering outperform the other methods but for symmetric and nearly symmetric 5-point matrices Multi-Color Block SOR gives the best performance, except for a few cases with a small number of processors.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.9.2578/_p
Salinan
@ARTICLE{e91-a_9_2578,
author={Sangback MA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Performance Comparison of the Parallel Preconditioners for Iterative Methods for Large Sparse Linear Systems Arising from Partial Differential Equations on Structured Grids},
year={2008},
volume={E91-A},
number={9},
pages={2578-2587},
abstract={In this paper we compare various parallel preconditioners such as Point-SSOR (Symmetric Successive OverRelaxation), ILU(0) (Incomplete LU) in the Wavefront ordering, ILU(0) in the Multi-color ordering, Multi-Color Block SOR (Successive OverRelaxation), SPAI (SParse Approximate Inverse) and pARMS (Parallel Algebraic Recursive Multilevel Solver) for solving large sparse linear systems arising from two-dimensional PDE (Partial Differential Equation)s on structured grids. Point-SSOR is well-known, and ILU(0) is one of the most popular preconditioner, but it is inherently serial. ILU(0) in the Wavefront ordering maximizes the parallelism in the natural order, but the lengths of the wavefronts are often nonuniform. ILU(0) in the Multi-color ordering is a simple way of achieving a parallelism of the order N, where N is the order of the matrix, but its convergence rate often deteriorates as compared to that of natural ordering. We have chosen the Multi-Color Block SOR preconditioner combined with direct sparse matrix solver, since for the Laplacian matrix the SOR method is known to have a nondeteriorating rate of convergence when used with the Multi-Color ordering. By using block version we expect to minimize the interprocessor communications. SPAI computes the sparse approximate inverse directly by least squares method. Finally, ARMS is a preconditioner recursively exploiting the concept of independent sets and pARMS is the parallel version of ARMS. Experiments were conducted for the Finite Difference and Finite Element discretizations of five two-dimensional PDEs with large meshsizes up to a million on an IBM p595 machine with distributed memory. Our matrices are real positive, i.e., their real parts of the eigenvalues are positive. We have used GMRES(m) as our outer iterative method, so that the convergence of GMRES(m) for our test matrices are mathematically guaranteed. Interprocessor communications were done using MPI (Message Passing Interface) primitives. The results show that in general ILU(0) in the Multi-Color ordering and ILU(0) in the Wavefront ordering outperform the other methods but for symmetric and nearly symmetric 5-point matrices Multi-Color Block SOR gives the best performance, except for a few cases with a small number of processors.},
keywords={},
doi={10.1093/ietfec/e91-a.9.2578},
ISSN={1745-1337},
month={September},}
Salinan
TY - JOUR
TI - A Performance Comparison of the Parallel Preconditioners for Iterative Methods for Large Sparse Linear Systems Arising from Partial Differential Equations on Structured Grids
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2578
EP - 2587
AU - Sangback MA
PY - 2008
DO - 10.1093/ietfec/e91-a.9.2578
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2008
AB - In this paper we compare various parallel preconditioners such as Point-SSOR (Symmetric Successive OverRelaxation), ILU(0) (Incomplete LU) in the Wavefront ordering, ILU(0) in the Multi-color ordering, Multi-Color Block SOR (Successive OverRelaxation), SPAI (SParse Approximate Inverse) and pARMS (Parallel Algebraic Recursive Multilevel Solver) for solving large sparse linear systems arising from two-dimensional PDE (Partial Differential Equation)s on structured grids. Point-SSOR is well-known, and ILU(0) is one of the most popular preconditioner, but it is inherently serial. ILU(0) in the Wavefront ordering maximizes the parallelism in the natural order, but the lengths of the wavefronts are often nonuniform. ILU(0) in the Multi-color ordering is a simple way of achieving a parallelism of the order N, where N is the order of the matrix, but its convergence rate often deteriorates as compared to that of natural ordering. We have chosen the Multi-Color Block SOR preconditioner combined with direct sparse matrix solver, since for the Laplacian matrix the SOR method is known to have a nondeteriorating rate of convergence when used with the Multi-Color ordering. By using block version we expect to minimize the interprocessor communications. SPAI computes the sparse approximate inverse directly by least squares method. Finally, ARMS is a preconditioner recursively exploiting the concept of independent sets and pARMS is the parallel version of ARMS. Experiments were conducted for the Finite Difference and Finite Element discretizations of five two-dimensional PDEs with large meshsizes up to a million on an IBM p595 machine with distributed memory. Our matrices are real positive, i.e., their real parts of the eigenvalues are positive. We have used GMRES(m) as our outer iterative method, so that the convergence of GMRES(m) for our test matrices are mathematically guaranteed. Interprocessor communications were done using MPI (Message Passing Interface) primitives. The results show that in general ILU(0) in the Multi-Color ordering and ILU(0) in the Wavefront ordering outperform the other methods but for symmetric and nearly symmetric 5-point matrices Multi-Color Block SOR gives the best performance, except for a few cases with a small number of processors.
ER -