×

An asynchronous direct solver for banded linear systems. (English) Zbl 1375.65046

Summary: Banded linear systems occur frequently in mathematics and physics. However, direct solvers for large systems cannot be performed in parallel without communication. The aim of this paper is to develop a general asymmetric banded solver with a direct approach that scales across many processors efficiently. The key mechanism behind this is that reduction to a row-echelon form is not required by the solver. The method requires more floating point calculations than a standard solver such as LU decomposition, but by leveraging multiple processors the overall solution time is reduced. We present a solver using a superposition approach that decomposes the original linear system into \(q\) subsystems, where \(q\) is the number of superdiagonals. These methods show optimal computational cost when \(q\) processors are available because each system can be solved in parallel asynchronously. This is followed by a \(q\times q\) dense constraint matrix problem that is solved before a final vectorized superposition is performed. Reduction to row echelon form is not required by the solver, and hence the method avoids fill-in. The algorithm is first developed for tridiagonal systems followed by an extension to arbitrary banded systems. Accuracy and performance is compared with existing solvers and software is provided in the supplementary material.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65Y15 Packaged methods for numerical algorithms
65Y05 Parallel numerical computation

Software:

MUMPS; PARDISO; LAPACK; MKL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amestoy, P.R., Duff, I.S., l’Excellent, J.-Y.: Multifrontal parallel distributed symmetric and unsymmetric solvers. Comput. Methods Appl. Mech. Eng. 184(2-4), 501-520 (2000) · Zbl 0956.65017 · doi:10.1016/S0045-7825(99)00242-X
[2] Amestoy, P.R., Duff, I.S., l’Excellent, J.-Y., Koster, J.: A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM J. Matrix Anal. Appl. 23(1), 15-41 (2001) · Zbl 0992.65018 · doi:10.1137/S0895479899358194
[3] Amestoy, P.R., Guermouche, A., l’Excellent, J.-Y., Pralet, S.: Hybrid scheduling for the parallel solution of linear systems. Parallel Comput. 32(2), 136-156 (2006) · doi:10.1016/j.parco.2005.07.004
[4] Bartels, R.H., Beatty, J.C., Barsky, B.A.: Hermite and Cubic Spline Interpolation. In: Ch. 3 in An Introduction to Splines for Use in Computer Graphics and Geometric Modelling. San Francisco, CA: Morgan Kaufmann, pp 9-17 (1998) · Zbl 0515.65022
[5] Demmel, J.W.: Applied Numerical Linear Algebra. SIAM, Philadelphia (1997) · Zbl 0879.65017
[6] Demmel, J.W., Gilbert, J.R., Li, X.S.: An Asynchronous Parallel Supernodal Algorithm for Sparse Gaussian Elimination. SIAM J. Matrix Anal. Appl. 20(4), 915952 (1999) · Zbl 0939.65036 · doi:10.1137/S0895479897317685
[7] Donfack, S., Dongarra, J., Faverge, M., Gates, M., Kurzak, J., Luszczek, P., Yamazaki, I.: A survey of recent developments in parallel implementations of Gaussian elimination, Concurrency and Computation: Practice and Experience. DOI: 10.1002/cpe.3306 (2014) · Zbl 0515.65022
[8] Duff, I., Reid, J.: The Multifrontal Solution of Indefinite Sparse Symmetric Linear Equations. ACM Trans. Math. Softw. 9(3), 302-325 (1983) · Zbl 0515.65022 · doi:10.1145/356044.356047
[9] Duff, I.: A review of frontal methods for solving linear systems. Comput. Phys. Commun. 97, 4552 (1996) · Zbl 0926.65030
[10] Gavel, D.T.: Solution to the Problem of Instability in Banded Toeplitz Solvers. IEEE Trans. Signal Process. 40, 464 (1992) · Zbl 1146.90055
[11] Golub, G., Van Loan, C.: Matrix Computations, 4th Edn. John Hopkins University Press, Baltimore, MD (2013) · Zbl 1268.65037
[12] Fortran ISML Numerical Library. User’s Guide, Version 7.0, Rogue Wave Software, 1315 West Century Drive, Suite 150, Louisville, CO 80027 (2010) · Zbl 0956.65017
[13] Irons, B.: A Frontal Solution Program for Finite Element Analysisss. Int. J. Numer. Methods Eng. 2, 5-32 (1970) · Zbl 0252.73050 · doi:10.1002/nme.1620020104
[14] Johnson, C.: Numerical Solution of Partial Differential Equations by the Finite Element Method, Dover Publications NY (2009) · Zbl 1191.65140
[15] Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.: LAPACK Users’ Guide, Third. In: Society for Industrial and Applied Mathematics. (paperback), pp 0-89871-447-8, Philadelphia, PA (1999) · Zbl 0934.65030
[16] Liu, J.: The Multifrontal Method for Sparse Matrix Solution. Theory and Practice, SIAM Review 34(1), 82-109 (1992) · Zbl 0919.65019
[17] Levinson, N.: The Wiener RMS (root mean square) error criterion in filter design and prediction. In: Wiener, N. (ed.) Extrapolation, Interpolation, and Smoothing of Stationary Time Series with Engineering Applications, pp 129-148. Wiley, Appendix B, New York (1949)
[18] Luisier, M., Schenk, O., et al: Fast Methods for Computing Selected Elements of the Green’s Function. In: Wolf, F., Mohr, B., an Ney, D. (eds.) Massively Parallel Nanoelectronic Device Simulations, Euro-Par 2013, LNCS 8097, pp 533-544. Springer-Verlag, Berlin Heidelberg (2013) · Zbl 0269.65018
[19] MacLeod, A.J.: Instability in the solution of banded Toeplitz systems. IEEE Trans. Acoust. Speech Signal Process. 37, 1449 (1989) · Zbl 0693.65017
[20] Mandel, J.: Balancing domain decomposition. Comm. Numer. Methods Engrg. 9, 233-241 (1993) · Zbl 0796.65126 · doi:10.1002/cnm.1640090307
[21] Meek, D.S.: The Inverses of Toeplitz Band Matrices. Linear Algebra Appl. 49, 117 (1983) · Zbl 0505.15005 · doi:10.1016/0024-3795(83)90097-6
[22] Intel Math Kernel Library, Reference Manual, Intel Corporation, 2200 Mission College Blvd., Santa Clara, CA 95052-8119, USA (2010)
[23] Ruffa, A.: A solution approach for lower Hessenberg linear systems. ISRN Applied Mathematics 2011, 236727 (2011) · Zbl 1242.65057 · doi:10.5402/2011/236727
[24] Ruffa, A., Jandron, M., Toni, B.: Parallelized Solution of Banded Linear Systems with an Introduction to p-adic Computation. In: Toni, B. (ed.) Mathematical Sciences with Multidisciplinary Applications Springer Proceedings in Mathematics & Statistics, vol. 157 (2016) · Zbl 1365.15009
[25] Schenk, O., Bollhoefer, M., Roemer, R.: On large-scale diagonalization techniques for the Anderson model of localization. Featured SIGEST paper in the SIAM Review selected on the basis of its exceptional interest to the entire SIAM community. SIAM Rev. 50, 91-112 (2008) · Zbl 1136.65044 · doi:10.1137/070707002
[26] Schenk, O., Waechter, A., Hagemann, M.: Matching-based Preprocessing Algorithms to the Solution of Saddle-Point Problems in Large-Scale Nonconvex Interior-Point Optimization. Journal of Computational Optimization and Applications 36(2-3), 321-341 (2007) · Zbl 1146.90055 · doi:10.1007/s10589-006-9003-y
[27] Stone, H. S.: An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations. J. Assoc. Comput. Mach. 20(1), 27-38 (1973) · Zbl 0269.65018 · doi:10.1145/321738.321741
[28] Thomas, L.H.: Elliptic Problems in Linear Differential Equations over a Network, Watson Sci. Comput. Lab Report. Columbia University, New York (1949) · Zbl 0939.65036
[29] Trench, W.F.: An algorithm for the inversion of finite Toeplitz smatrices. J. Soc. Ind. Appl. Math. 12, 515 (1964) · Zbl 0269.65018
[30] Van der Vorst, H.A.: Analysis of a parallel solution method for tridiagonal linear systems 5(3), 303311 (1987) · Zbl 0641.65020
[31] Zohar, S.: The solution of a Toeplitz set of linear equations. J. ACM 21, 272 (1974) · Zbl 0276.65014 · doi:10.1145/321812.321822
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.