An efficient approach to solve very large dense linear systems with verified computing on clusters. (English) Zbl 1363.65088
Summary: Automatic result verification is an important tool to guarantee that completely inaccurate results cannot be used for decisions without getting remarked during a numerical computation. Mathematical rigor provided by verified computing allows the computation of an enclosure containing the exact solution of a given problem. Particularly, the computation of linear systems can strongly benefit from this technique in terms of reliability of results. However, in order to compute an enclosure of the exact result of a linear system, more floating-point operations are necessary, consequently increasing the execution time. In this context, parallelism appears as a good alternative to improve the solver performance. In this paper, we present an approach to solve very large dense linear systems with verified computing on clusters. This approach enabled our parallel solver to compute huge linear systems with point or interval input matrices with dimensions up to 100,000. Numerical experiments show that the new version of our parallel solver introduced in this paper provides good relative speedups and delivers a reliable enclosure of the exact results.
MSC:
| 65G20 | Algorithms with automatic result verification |
| 65F05 | Direct numerical methods for linear systems and matrix inversion |
| 65Y05 | Parallel numerical computation |
| 65G30 | Interval and finite arithmetic |
Keywords:
interval arithmetic; verified computing; linear systems; parallel algorithms; BLAS; ScaLAPACK; PBLAS; LAPACK; C-XSC; Matlab; INTLAB; PLASMA; MAGMA; automatic result verification; numerical experimentsSoftware:
PBLAS; Cosy; PLASMA; LAPACK; C-XSC; MPI; BLAS; INTLAB; ScaLAPACK; C-XSC 2.0; MAGMA; PLASMA; MatlabReferences:
| [1] | BaboulinM, GiraudL, GrattonS. A parallel distributed solver for large dense symmetric systems: applications to geodesy and electromagnetism problems. International Journal of High Speed Computing2005; 19(4):353-363. |
| [2] | StpiczynskiP, PaprzyckiM. Numerical software for solving dense linear algebra problems on high performance computers. APLIMAT 2005: Proceedings of the 4th International Conference on Applied Mathematics, Bratislava, Slovak Republic, 2005; 207-218. |
| [3] | ZhangJ, MapleC. Parallel solutions of large dense linear systems using MPI. In PARELEC ’02: Proceedings of the International Conference on Parallel Computing in Electrical Engineering. IEEE Computer Society Press: Warsaw, Poland, 2002; 312-317. |
| [4] | RumpSM. Verification methods: Rigorous results using floating‐point arithmetic. Acta Numerica2010; 19:287-449. · Zbl 1323.65046 |
| [5] | KearfottRB. Interval Computations: Introduction, Uses and Resources. Euromath Bulletin1996; 2(1). · Zbl 1465.65041 |
| [6] | RumpSM. Fast and Parallel Interval Arithmetic. Bit Numerical Mathematics1999; 39(3):534-554. · Zbl 0942.65048 |
| [7] | RumpSM. INTLAB—INTerval LABoratory. In Developments in Reliable Computing, CsendesT (ed.) (ed.). Kluwer Academic Publisher: Dordrecht, 1999; 77-104. · Zbl 0949.65046 |
| [8] | KolbergM, BaldoL, VelhoP, FernandesLG, ClaudioD. Optimizing a parallel self‐verified method for solving linear systems. In PARA 2006: Applied Parallel Computing. State of the Art in Scientific Computing, vol. 4699, Lecture Notes in Computer Science. Springer Berlin/Heidelberg: Germany, 2008; 949-955. |
| [9] | KolbergM, BaldoL, VelhoP, WebberT, FernandesLG, FernandesP, ClaudioD. Parallel self‐verified method for solving linear systems. In VECPAR 2006: 7th International Meeting on High Performance Computing for Computational Science, Rio de Janeiro: Brazil, 2006; 179-190. |
| [10] | KolbergM, BohlenderG, ClaudioD. Improving the performance of a verified linear system solver using optimized libraries and parallel computation. In VECPAR 2008: High Performance Computing for Computational Science, vol. 5336, Lecture Notes in Computer Science. Springer Berlin/Heidelberg: Germany, 2008; 13-26. |
| [11] | KolbergM, DornM, FernandesLG, BohlenderG. Parallel verified linear system solver for uncertain input data. 20th International Symposium on Computer Architecture and High Performance Computing, SBAC‐PAD 2008, IEEE Computer Society, Campo Grande, Brazil, 2008; 89-96. |
| [12] | KolbergM, FernandesLG, ClaudioD. Dense linear system: a parallel self‐verified solver. International Journal of Parallel Programming2008; 36:412-425. · Zbl 1154.68361 |
| [13] | BakerM, BuyyaR. Cluster computing: the commodity supercomputer. Software‐Practice and Experience1999; 29:551-576. |
| [14] | HedayatGA. Numerical linear algebra and computer architecture: an evolving interaction. Technical Report UMCS‐93‐1‐5, University of Manchester: Manchester, England, 1993. |
| [15] | SaadY. Iterative Methods for Sparse Linear Systems. PWS Publishing Company: Boston, 1995. |
| [16] | D’AzevedoE, DongarraJ. The design and implementation of the parallel out‐of‐core ScaLAPACK LU, QR, and Cholesky factorization routines. Concurrency—Practice and Experience2000; 12(15):1481-1493. · Zbl 1008.68577 |
| [17] | KlatteR, KulischU, LawoC, RauchR, WiethoffA. C‐XSC‐ A C++ Class Library for Extended Scientific Computing. Springer‐Verlag: Berlin, 1993. · Zbl 0814.68035 |
| [18] | RumpSM. Kleine Fehlerschranken bei Matrixproblemen. PhD thesis, University of Karlsruhe, Germany, 1980. · Zbl 0437.65036 |
| [19] | FengT, FlueckAJ. AMessage‐Passing Distributed‐Memory Newton‐GMRES Parallel Power Flow Algorithm. Proceedings of the IEEE Power Engineering Society Summer Meeting, IEEE Press, Vol. 3, Chicago, USA, 2002; 1477-1482. |
| [20] | DemmelJW, HeathMT, van derVorstHA. Parallel Numerical Linear Algebra. Technical Report UCB CSD‐92‐703, Cambridge University, 1993. |
| [21] | LAPACK. LAPACK Users’ Guide, 2013. (Available from: http://www.netlib.org/lapack/lug/.visited) [accessed on 19th April 2013]. |
| [22] | DongarraJ, Du CrozJ, DuffIS, HammarlingS. A Set of Level 3 Basic Linear Algebra Subprograms. ACM Transactions on Mathematical Software1990; 16:1-17. · Zbl 0900.65115 |
| [23] | DongarraJ, PozoR, WalkerDW. LAPACK++: a design overview of object‐oriented extensions for high performance linear algebra. In SUPERCOMPUTING ’93: Proceedings of the 1993 ACM/IEEE conference on Supercomputing. IEEE Computer Society Press: Portland, USA, 1993; 162-171. |
| [24] | MathWorks. MATLAB, The Language of Technical Computing. The MathWorks, Inc.: Natick, 2001. |
| [25] | INTLAB. INTerval LABoratory, 2013. (Available from: http://www.ti3.tu‐harburg.de/rump/intlab/.visited) [19th April 2013]. |
| [26] | ZimmerM, KrämerW, BohlenderG, HofschusterW. Extension of the C‐XSC library with scalar products with selectable accuracy. Technical Report BUW‐WRSWT 2009/4, Universität Wuppertal, Wuppertal: Germany, 2009. |
| [27] | RumpSM, Accurate and reliable computing in floating‐point arithmetic. In Proceedings of the Third International Congress on Mathematical Software, Kobe, Japan, September 13-17, 2010 (ICMS 2010), vol. 6327, Lecture Notes in Computer Science. Springer Berlin / Heidelberg: Germany, 2010; 105-108. · Zbl 1295.65133 |
| [28] | RumpSM. Fast interval matrix multiplication, to be published in Numerical Algorithms, 2012. |
| [29] | NguyenHD, RevolN. Accuracy issues in linear algebra using interval arithmetic. SCAN 2010: 14th GAMM‐IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, Lyon, France, 2010. |
| [30] | NguyenHD, RevolN. High performance linear algebra using interval arithmetic. PASCO 2010, Grenoble, France, 2010; 171-172. |
| [31] | NguyenHD, RevolN. Refining and verifying efficiently the solution of a linear system. Dagstuhl Seminar 11371: Uncertainty Modeling and Analysis with Intervals: Foundations, Tools, Applications, Dagstuhl, Germany, September 2011; 11-16. |
| [32] | FaciusA. Iterative Solution of linear systems with improved arithmetic and result verification. PhD thesis, University of Karlsruhe, Germany, 2000. |
| [33] | KerstenT. Verifizierende Rechnerinvariante Numerikmodule. PhD thesis, University of Karlsruhe, Germany, 1998. |
| [34] | WiethoffA. Verifizierte Globale Optimierung auf Parallelrechnern. PhD thesis, University of Karlsruhe, Germany, 1997. |
| [35] | KolbergM, KrämerW, ZimmerM. Efficient parallel solvers for large dense systems of linear interval equations. Reliable Computing2011; 15(3):193-206. |
| [36] | KrämerW, ZimmerM. Fast (parallel) dense linear system solvers in C‐XSC using error free transformations and BLAS. In Numerical Validation in Current Hardware Architectures, vol. 5492, Lecture Notes in Computer Science. Springer Berlin/Heidelberg: Germany, 2009; 230-249. |
| [37] | P1788. IEEE Standard for Interval Arithmetic. (Available from: http://grouper.ieee.org/groups/1788/PositionPapers/VanSnyderP1788.pdf.visited) [19th April 2013]. |
| [38] | NeumaierA. Improving interval enclosures., Reliable Computing, to appear. |
| [39] | BohlenderG. What do we need beyond IEEE arithmetic?. In Computer Arithmetic and Self‐validating Numerical Methods, ChristianUllrich (ed.) (ed.). Academic Press Professional, Inc.: San Diego, CA, USA, 1990; 1-32. · Zbl 0717.65025 |
| [40] | KulischU, MirankerWL. Computer Arithmetic in Theory and Practice. Academic Press: New York, 1981. · Zbl 0487.65026 |
| [41] | OgitaT, RumpSM, OishiS. Verified solution of linear systems without directed rounding. Technical Report 2005‐04, Advanced Research Institute for Science and Engineering, Waseda University, Tokyo, Japan, 2005. |
| [42] | RevolN, MakinoK, BerzM. Taylor models and floating‐point arithmetic: proof that arithmetic operations are validated in COSY. Technical Report INRIA RR‐4737, 2003. |
| [43] | HammerR, RatzD, KulischU, HocksM. C++ Toolbox for Verified Scientific Computing I: Basic Numerical Problems. Springer‐Verlag New York: Secaucus, NJ, USA, 1997. |
| [44] | AlefeldG, HerzbergerJ. Introduction to Interval Computations. Academic Press: New York, 1983. · Zbl 0552.65041 |
| [45] | KolbergM, CordeiroD, BohlenderG, FernandesLG, GoldmanA. A Multithreaded Verified Method for Solving Linear Systems in Dual‐core Processors. In PARA—9th International Workshop on State‐of‐the‐Art in Scientific and Parallel Computing, To be published, Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 2008. |
| [46] | AgulloE, DongarraJ, HadriB, KurzakJ, LangouJ, LtaiefH, LuszczekP, YarKhanA. PLASMA Users Guide, visited 19th, April 2013. |
| [47] | MilaniC, KolbergM, FernandesLG. Solving dense interval linear systems with verified computing on multicore architectures. In VECPAR 2010: High Performance Computing for Computational Science, vol. 6449, Lecture Notes in Computer Science. Springer Berlin / Heidelberg: Germany, 2010; 435-448. · Zbl 1323.65137 |
| [48] | TomovS, NathR, DuP, DongarraJ. MAGMA users guide. (Available from: http://icl.cs.utk.edu/projectsfiles/magma/docs/magma‐v02.pdf.visited) [accessed on 19th April 2013]. |
| [49] | SnirM, OttoS, Huss‐LedermanS, WalkerDW, DongarraJ. MPI: The Complete Reference. MIT Press: Cambridge, MA, 1996. |
| [50] | DongarraJ, WalkerD. LAPACK working note 58: the design of linear algebra libraries for high performance computers. Technical Report UT‐CS‐93‐188: Knoxville, TN, USA, 1993. |
| [51] | BlackfordLS, ChoiJ, ClearyA, DemmelJ, DhillonI, DongarraJ, Ham‐ marlingS, HenryG, APetitet, StanleyK, WalkerD, WhaleyRC. ScaLAPACK: a portable linear algebra library for distributed memory computers design issues and performance. SUPERCOMPUTING ’96: Proceedings of the 1996 ACM/IEEE Conference on Supercomputing, IEEE Computer Society Press, Pittsburgh, Pennsylvania, USA, 1996. · Zbl 0926.65148 |
| [52] | ChoiJ, DemmelJ, DhillonI, DongarraJ, OstrouchovS, PetitetA, StanleyK, WalkerD, Whaley LAPACK working note 95RC. ScaLAPACK: a portable linear algebra library for distributed memory computers—design issues and Performance. Technical Report UT‐CS‐95‐283, University of Tennessee, Knoxville, TN, USA, 1995. |
| [53] | KolbergM, RockerB, HeuvelineV. The impact of data distribution in accuracy and performance of parallel linear algebra subroutines. In VECPAR 2010: High Performance Computing for Computational Science, vol. 6449, Lecture Notes in Computer Science. Springer Berlin / Heidelberg: Germany, 2010; 394-407. · Zbl 1323.65131 |
| [54] | ToledoS. Asurvey of out‐of‐core algorithms in numerical linear algebra. External Memory Algorithms, American Mathematical Society Boston, USA, 1999; 161-179. · Zbl 0943.65036 |
| [55] | GregoryRT, KarneyDL. A Collection of Matrices for Testing Computational Algorithms. Wiley‐Interscience: New York, 1969. · Zbl 0195.44803 |
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.
