×

Efficient high-precision matrix algebra on parallel architectures for nonlinear combinatorial optimization. (English) Zbl 1200.65045

Summary: We provide a first demonstration of the idea that matrix-based algorithms for nonlinear combinatorial optimization problems can be efficiently implemented. Such algorithms were mainly conceived by theoretical computer scientists for proving efficiency. We are able to demonstrate the practicality of our approach by developing an implementation on a massively parallel architecture, and exploiting scalable and efficient parallel implementations of algorithms for ultra high-precision linear algebra. Additionally, we have delineated and implemented the necessary algorithmic and coding changes required in order to address problems several orders of magnitude larger, dealing with the limits of scalability from memory footprint, computational efficiency, reliability, and interconnect perspectives.

MSC:

65K05 Numerical mathematical programming methods
90C27 Combinatorial optimization
90C26 Nonconvex programming, global optimization
65Y05 Parallel numerical computation
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alam, S., Barrett, R., Bast, M., Fahey, M.R., Kuehn, J., McCurdy, C., Rogers, J., Roth, P., Sankaran, R., Vetter, J.S., Worley, P., Yu, W.: Early evaluation of IBM BlueGene/P, SC ’08. In: Proceedings of the 2008 ACM/IEEE Conference on Supercomputing, pp 1–12 (2008)
[2] Almási G., Archer C., Castaños J.G., Gunnels J.A., Erway C.C., Heidelberger P., Martorell X., Moreira J.E., Pinnow K., Ratterman J., Steinmacher-Burow B.D., Gropp W., Toonen B.: Design and implementation of message-passing services for the Blue Gene/L supercomputer. IBM. J. Res. Dev. 49(2–3), 393–406 (2005) · Zbl 05420204 · doi:10.1147/rd.492.0393
[3] ARPREC. http://crd.lbl.gov/\(\sim\)dhbailey/mpdist/mpdist.html
[4] Bailey D.H.: High-precision arithmetic in scientific computation. Comput. Sci. Eng. 7(3), 54–61 (2005) · Zbl 05092091 · doi:10.1109/MCSE.2005.52
[5] Bailey, D.H., Borwein, J.M.: Highly Parallel, High-Precision Numerical Integration. LBNL-57491 (2005)
[6] Berstein Y., Lee J., Maruri-Aguilar H., Onn S., Riccomagno E., Weismantel R., Wynn H.: Nonlinear matroid optimization and experimental design. SIAM J. Discret. Math. 22(3), 901–919 (2008) · Zbl 1198.05024 · doi:10.1137/070696465
[7] Berstein, Y., Lee, J., Onn, S., Weismantel, R.: Parametric nonlinear discrete optimization over well-described sets and matroid intersections. Math. Program. (to appear) · Zbl 1198.90334
[8] Buttari A., Dongarra J., Langou J., Langou J., Luszczek P., Kurzak J.: Mixed precision iterative refinement techniques for the solution of dense linear systems. Int. J. High. Perform. Comput. Appl. 21(4), 457–466 (2007) · Zbl 1197.65240 · doi:10.1177/1094342007084026
[9] Chiu, G.L.-T., Gupta, M., Royyuru, A.K. (guest eds.): Blue Gene. IBM J. Res. Dev. 49(2/3) (2005)
[10] Choi J., Dongarra J., Ostrouchov S., Petitet A., Walker D., Whaley C.: Design and implementation of the ScaLAPACK LU, QR, and Cholesky factorization routines. Sci. Program. 5(3), 173–184 (1996)
[11] De Loera, J., Haws, D.C., Lee, J., O’Hair, A.: Computation in multicriteria matroid optimization. ACM J. Exp. Algorithmics 14, Article No. 8, (2009) · Zbl 1284.68226
[12] Demmel, J.: The future of LAPACK and ScaLAPACK, PARA 06: workshop on State-of-the-Art. In: Scientific and Parallel Computing, Umea, Sweden, 18–21 June 2006. http://www.cs.berkeley.edu/\(\sim\)demmel/cs267_Spr07/future_sca-lapack_CS267_Spr07.ppt
[13] Eisinberg A., Fedele G., Imbrogno C.: Vandermonde systems on equidistant nodes in [0, 1]: accurate computation. Appl. Math. Comput. 172, 971–984 (2006) · Zbl 1089.65022 · doi:10.1016/j.amc.2005.02.020
[14] Eisinberg A., Franzé G., Pugliese P.: Vandermonde matrices on integer nodes. Numerische Mathematik 80(1), 75–85 (1998) · Zbl 0913.65022 · doi:10.1007/s002110050360
[15] Fries A., Hunter W.G.: Minimum aberration 2 k-p designs. Technometrics 22, 601–608 (1980) · Zbl 0453.62063 · doi:10.2307/1268198
[16] Harvey, N.: Algebraic algorithms for matching and matroid problems. SIAM J. Comput. (2010, to appear)
[17] Higham N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2002) · Zbl 1011.65010
[18] IBM Blue Gene Team: Overview of the IBM Blue Gene/P project, IBM J. Res. Dev., v52, (2008), 199–220
[19] Lee, J.: A First Course in Combinatorial Optimization. Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge (2004) · Zbl 1089.90044
[20] Lee J., Ryan J.: Matroid applications and algorithms. INFORMS (formerly ORSA) J. Comput. 4, 70–98 (1992) · Zbl 0767.90072
[21] mStirling.c. http://ftp.bioinformatics.org/pub/pgetoolbox/addins/src/mStirling.c
[22] Mulmuley K., Vazirani U.V., Vazirani V.V.: Matching is as easy as matrix inversion. Combinatorica 7, 105–113 (1987) · Zbl 0632.68041 · doi:10.1007/BF02579206
[23] Oxley J.G.: Matroid Theory. Oxford Science Publications, The Clarendon Press, Oxford University Press, New York (1992) · Zbl 0784.05002
[24] Pistone, G., Riccomagno, E., Wynn, H.P.: Algebraic Statistics. Monographs on Statistics and Applied Probability, vol. 89. Chapman & Hall/CRC, Boca Raton (2001) · Zbl 0960.62003
[25] Recski A.: Matroid theory and its applications in electric network theory and in statics. Springer, Berlin (1989) · Zbl 0729.05012
[26] Tweddle, I.: James Stirling’s methodus differentialis: an annotated translation of Stirling’s text. In: Sources and Studies in the History of Mathematics and Physical Sciences, Springer (2003) · Zbl 1031.01008
[27] van de Geijn R.A., Watts J.: SUMMA: scalable universal matrix multiplication algorithm. Concurr. Pract. Experience 9(4), 255–274 (1997) · Zbl 05472339 · doi:10.1002/(SICI)1096-9128(199704)9:4<255::AID-CPE250>3.0.CO;2-2
[28] VanInverse.m. http://www.mathworks.com/matlabcentral/files/8048/VanInverse.m
[29] Wu H., Wu C.F.J.: Clear two-factor interactions and minimum aberration. Ann. Stat. 30, 1496–1511 (2002) · Zbl 1015.62083 · doi:10.1214/aos/1035844985
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.