Solving dense interval linear systems with verified computing on multicore architectures. (English) Zbl 1323.65137

Palma, José M. Laginha M. (ed.) et al., High performance computing for computational science – VECPAR 2010. 9th international conference, Berkeley, CA, USA, June 22–25, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-19327-9/pbk). Lecture Notes in Computer Science 6449, 435-448 (2011).
Summary: Automatic result verification is an important tool to reduce the impact of floating-point errors in numerical computation and to guarantee the mathematical rigor of results. One fundamental problem in Verified Computing is to find an enclosure that surely contains the exact result of a linear system. Many works have been developed to optimize Verified Computing algorithms using parallel programming techniques and message passing paradigm on clusters of computers. However, the High Performance Computing scenario changed considerably with the emergence of multicore architectures in the past few years. This paper presents an ongoing research project which has the purpose of developing a self-verified solver for dense interval linear systems optimized for parallel execution on these new architectures. The current version has obtained up to 85% of reduction at execution time and a speedup of 6.70 when solving a \(15,000 \times 15,000\) interval linear system on an eight core computer.
For the entire collection see [Zbl 1207.68016].


65Y10 Numerical algorithms for specific classes of architectures
65F05 Direct numerical methods for linear systems and matrix inversion
65G20 Algorithms with automatic result verification
65G30 Interval and finite arithmetic
65Y05 Parallel numerical computation
65Y20 Complexity and performance of numerical algorithms
Full Text: DOI


[1] Hayes, B.: A Lucid Interval. American Scientist 91(6), 484–488 (2003)
[2] Hammer, R., Ratz, D., Kulisch, U., Hocks, M.: C++ Toolbox for Verified Scientific Computing I: Basic Numerical Problems. Springer, New York (1997) · Zbl 0828.68041
[3] Kolberg, M., Dorn, M., Bohlender, G., Fernandes, L.G.: Parallel Verified Linear System Solver for Uncertain Input Data. In: Proceedings of 20th SBAC-PAD - International Symposium on Computer Architecture and High Performance Computing, pp. 89–96 (2008)
[4] Kearfott, R.: Interval Computations: Introduction, Uses, and Resources. Euromath Bulletin 2(1), 95–112 (1996)
[5] Demmel, J.: LAPACK: A Portable Linear Algebra Library for Supercomputers. In: Proceedings of IEEE Control Systems Society Workshop on Computer-Aided Control System Design, pp. 1–7 (1989)
[6] Choi, J., Demmel, J., Dhillon, I., Dongarra, J., Ostrouchov, S., Petitet, A., Stanley, K., Walker, D., Whaley, R.: ScaLAPACK: a Portable Linear Algebra Library for Distributed Memory Computers – Design Issues and Performance. Computer Physics Communications 97(1-2), 1–15 (1996) · Zbl 0926.65148
[7] Kolberg, M., Baldo, L., Velho, P., Fernandes, L.G., Claudio, D.: Optimizing a Parallel Self-verified Method for Solving Linear Systems. In: Kågström, B., Elmroth, E., Dongarra, J., Waśniewski, J. (eds.) PARA 2006. LNCS, vol. 4699, pp. 949–955. Springer, Heidelberg (2007)
[8] Kolberg, M., Fernandes, L.G., Claudio, D.: Dense Linear System: A Parallel Self-verified Solver. International Journal of Parallel Programming 36(4), 412–425 (2008) · Zbl 1154.68361
[9] Buttari, A., Dongarra, J., Kurzak, J., Langou, J., Luszczek, P., Tomov, S.: The Impact of Multicore on Math Software. In: Kågström, B., Elmroth, E., Dongarra, J., Waśniewski, J. (eds.) PARA 2006. LNCS, vol. 4699, pp. 1–10. Springer, Heidelberg (2007)
[10] TOP 500 Supercomputing Home Page, http://www.top500.org/ (accessed on December 11, 2009)
[11] Agullo, E., Hadri, B., Ltaief, H., Dongarra, J.: Comparative Study of One-Sided Factorizations with Multiple Software Packages on Multi-Core Hardware. LAPACK Working Note 217, ICL, UTK (2009)
[12] Chan, E., Van Zee, F., Bientinesi, P., Quintana-Orti, E., Quintana-Orti, G., van de Geijn, R.: SuperMatrix: a Multithreaded Runtime Scheduling System for Algorithms-by-blocks. In: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 123–132 (2008)
[13] Gunnels, J., Gustavson, F., Henry, G., van de Geijn, R.: FLAME: Formal Linear Algebra Methods Environment. ACM Transactions on Mathematical Software 27(4), 422–455 (2001) · Zbl 1070.65522
[14] Rump, S.M.: Fast and Parallel Interval Arithmetic. BIT Numerical Mathematics 39(3), 534–554 (1999) · Zbl 0942.65048
[15] Intel Math Kernel Library Home Page, http://software.intel.com/en-us/intel-mkl/ (accessed on December 11, 2009)
[16] Lawson, C., Hanson, R., Kincaid, D., Krogh, F.: Basic Linear Algebra Subprograms for Fortran Usage. ACM Transactions on Mathematical Software 5(3), 308–323 (1979) · Zbl 0412.65022
[17] Klatte, R., Kulisch, U., Lawo, C., Rauch, R., Wiethoff, A.: C-XSC - A C++ Class Library for Extended Scientific Computing. Springer, Heidelberg (1993) · Zbl 0814.68035
[18] Kolberg, M., Cordeiro, D., Bohlender, G., Fernandes, L.G., Goldman, A.: A Multithreaded Verified Method for Solving Linear Systems in Dual-Core Processors. In: 9th PARA - International Workshop on State-of-the-Art in Scientific and Parallel Computing, Trondheim - Noruega. PARA 2008 - Revised Selected Papers. LNCS. Springer, Heidelberg (2008) (to appear)
[19] Kolberg, M., Bohlender, G., Claudio, D.M.: Improving the Performance of a Verified Linear System Solver Using Optimized Libraries and Parallel Computing. In: Palma, J.M.L.M., Amestoy, P.R., Daydé, M., Mattoso, M., Lopes, J.C. (eds.) VECPAR 2008. LNCS, vol. 5336, pp. 13–26. Springer, Heidelberg (2008) · Zbl 05502080
[20] Butenhof, D.R.: Programming with POSIX Threads. Addison-Wesley Longman Publishing Co., Inc., Boston (1997)
[21] Rump, S.M.: Self-validating Methods. Linear Algebra and Its Applications 324(1-3), 3–13 (2001) · Zbl 0978.65037
[22] ANSI/IEEE. A Standard for Binary Floating-point Arithmetic, Std.754-1985. American National Standards Institute / Institute of Electrical and Eletronics Engineers. USA (1985)
[23] PLASMA README, http://icl.cs.utk.edu/projectsfiles/plasma/html (accessed on April 8, 2010)
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.