Effect of the storage format of sparse linear systems on parallel CFD computations. (English) Zbl 0971.76045

Summary: Implicit solutions of computational fluid dynamics (CFD) problems require iterative solution of very large systems of equations. This paper investigates the comparative costs of two storage formats for large sparse matrices, namely the compressed sparse row (CSR) and BSR storage formats, for various solution strategies. The block structure of the BSR storage format is highly advantageous in applications which have several degrees of freedom per nodal point, such as CFD calculations. Depending on the solution strategy, overall reductions in both CPU time and memory can be as high as 30-50%. Such gains are especially appreciable in large three-dimensional flow calculations.


76M10 Finite element methods applied to problems in fluid mechanics
65G50 Roundoff error
Full Text: DOI


[1] Anderson, E.C.; Saad, Y., Solving sparse triangular systems on parallel computers, Internat. J. high speed comp., 1, 73-96, (1989) · Zbl 0726.65026
[2] E. Anderson et al., LAPACK Users’ Guide, SIAM, Philadelphia, 1992 · Zbl 0755.65028
[3] S.Balay, W. Gropp, L. Curfman McInnes, B. Smith, PETSc 2.0 Users Manual, Technical Report ANL, 95/11, Argonne National Laboratory, Argonne, IL, USA, 1995
[4] A. Chapman, Y. Saad, L. Wigton, High-Order ILU Preconditioners for CFD Problems, Technical Report UMSI 96/14, University Minnesota Supercomp. Inst., Minneapolis, MN 55415, February 1996 · Zbl 0959.76077
[5] E.H. Cuthill, J.M. McKee, Reducing the Bandwith of Sparse Symmetric Matrices, in: Proceedings of 24th National Conference of the Association for Computing Machinery, Brondon Press, New Jersey, 1969, pp. 157-172
[6] Dutto, L.C., The effect of ordering on preconditioned GMRES algorithm for solving the compressible navier – stokes equations, Int. J. numer. methods engrg., 36, 3, 457-497, (1993) · Zbl 0767.76026
[7] L.C. Dutto, W.G. Habashi, Parallelization of the ILU(0) Preconditioner for CFD problems on shared-memory computers, Int. J. Numer. Methods Fluids 30 (1999) 995-1008 · Zbl 0970.76078
[8] Dutto, L.C.; Habashi, W.G.; Fortin, M., Parallelizable block diagonal preconditioners for the compressible navier – stokes equations, Comput. methods appl. mech. engrg., 117, 15-47, (1994) · Zbl 0847.76032
[9] Dutto, L.C.; Habashi, W.G.; Fortin, M., An algebraic multilevel parallelizable preconditioner for large-scale CFD problems, Comput. methods appl. mech. engrg., 149, 303-318, (1997) · Zbl 0923.76247
[10] Dutto, L.C.; Habashi, W.G.; Robichaud, M.P.; Fortin, M., A method for finite element parallel viscous compressible flow calculations, Int. J. numer. methods fluids, 19, 275-294, (1994) · Zbl 0815.76042
[11] Freund, R.W., A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems, SIAM J. sci. stat. comput., 14, 2, 470-482, (1993) · Zbl 0781.65022
[12] A. George, Computer implementation of the finite element method, Ph.D. Thesis, Department of Computer Science, Stanford University Stanford, USA, 1971, Also as Research Report STAN CS-71-208, Stanford University, Stanford, USA
[13] W.G. Habashi (Ed.), Solution Techniques for large-scale CFD problems, chapter Parallel Finite Element Computation of 3D Compressible Turbomachinery Flows on Workstation Clusters, Computational Methods in Applied Sciences, Wiley, New York, 1995, pp. 41-56
[14] Hendrickson, B.; Leland, R., An improved spectral graph partitioning algorithm for mapping parallel computations, SIAM J. sci. comput., 16, 2, 452-469, (1995) · Zbl 0816.68093
[15] M.A. Heroux, A proposal for a sparse BLAS toolkit, SPARKER Working Note 2, CERFACS, TR/PA/92/90, Technical Report, 1992
[16] Kincaid, D.R.; Respess, J.R.; Young, D.M.; Grimes, R.G., Algorithm 586 - ITPACK 2C: A FORTRAN package for solving large sparse linear systems by adaptive accelerated iterative methods, ACM trans. math. software, 8, 3, 302-322, (1982) · Zbl 0485.65025
[17] Pommerell, C.; Fichtner, W., Memory aspects and performance of iterative solvers, SIAM J. sci. stat. comput., 15, 2, 460-473, (1994) · Zbl 0798.65045
[18] Y. Saad, SPARSKIT: A basic tool kit for sparse matrix computations, Technical Report 90-20, Research Inst. Adv. Comp. Science, NASA Ames Research Center, Moffett Field, CA, USA, 1990
[19] Y. Saad, A.V. Malevsky, P-SPARSLIB: A portable library of distributed memory sparse iterative solvers, in: V. E. Malyshkin et al. (Eds.), Proceedings of Parallel Computing Technologies (PaCT-95), 3rd International Conference, St. Petersburg, Russia, September 1995
[20] Saad, Y.; Schultz, M.H., GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. sci. stat. comput., 7, 856-869, (1986) · Zbl 0599.65018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.