×

A parallel algorithm for calculation of determinants and minors using arbitrary precision arithmetic. (English) Zbl 1338.65117

Summary: We present a parallel algorithm for calculating determinants of matrices in arbitrary precision arithmetic on computer clusters. This algorithm limits data movements between the nodes and computes not only the determinant but also all the minors corresponding to a particular row or column at a little extra cost, and also the determinants and minors of all the leading principal submatrices at no extra cost. We implemented the algorithm in arbitrary precision arithmetic, suitable for very ill-conditioned matrices, and empirically estimated the loss of precision. In our scenario the cost of computation is bigger than that of data movement. The algorithm was applied to studies of Riemann’s zeta function.

MSC:

65F40 Numerical computation of determinants
65Y05 Parallel numerical computation
65D20 Computation of special functions and constants, construction of tables
11M06 \(\zeta (s)\) and \(L(s, \chi)\)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abdelmalek, S., Kouachi, S.: Condensation of determinants. ArXiv: http://arxiv.org/abs/0712.0822 (2007) · Zbl 1155.35384
[2] Agullo, E., Demmel, J., Dongarra, J., Hadri, B., Kurzak, J., Langou, J., Ltaief, H., Luszczek, P., Tomov, S.: Numerical linear algebra on emerging architectures: the PLASMA and MAGMA projects. J. Phys. Conf. Ser. 180, 012037 (2009)
[3] Ballard, G., Demmel, J., Holtz, O., Schwartz, O.: Minimizing communication in numerical linear algebra. SIAM J. Matrix Anal. Appl. 32, 866-901 (2011) · Zbl 1246.68128
[4] Beliakov, G., Matiyasevich, Yu.: Approximation of Riemann’s zeta function by finite Dirichlet series: multiprecision numerical approach. Exp. Math. 24, 1-12 (2015). doi:10.1080/10586458.2014.976801, Preliminary version. http://arxiv.org/abs/1402.5295 · Zbl 1381.11075
[5] Blackford, L.S., Choi, J., Cleary, A., D’Azevedo, E., Demmel, J., Dhillon, I., Dongarra, J., Hammarling, S., Henry, G., Petitet, A., Stanley, K., Walker, D., Whaley, R.C.: ScaLAPACK Users’ Guide. Society for Industrial and Applied Mathematics, Philadelphia (1997) · Zbl 0886.65022
[6] Borwein, P., Choi, S., Rooney, B., et al. (eds.): The Riemann hypothesis: a resource for the afficionado and virtuoso alike. In: CMS Books in Mathematics. Springer, New York (2008) · Zbl 1132.11047
[7] Buttari, A., Langou, J., Kurzak, J., Dongarra, J.: A class of parallel tiled linear algebra algorithms for multicore architectures. Parallel Comput. 35, 38-53 (2009)
[8] Cannon, L.E.: A cellular computer to implement the Kalman filter algorithm. PhD thesis, Montana State University, Bozeman (1969) · Zbl 1241.65028
[9] Clay Institute: The millennium prize problems (2013). http://www.claymath.org/millennium-problems. Accessed 15 Dec 2014
[10] Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 251-280 (1990) · Zbl 0702.65046
[11] Demmel, J., Grigori, L., Hoemmen, M., Langou, J.: Communication-optimal parallel and sequential QR and LU factorizations. SIAM J. Sci. Comput. 34, A206-A239 (2012) · Zbl 1241.65028
[12] Dodgson, C.L.: Condensation of determinants. Proc. Royal Soc. Lond. 15, 150-155 (1866)
[13] Fousse, L., Hanrot, G., Lefèvre, V., Pélissier, P., Zimmermann P. MPFR: a multiple-precision binary floating-point library with correct rounding. ACM Trans. Math. Softw. 33, 13:1-13:15 (2007) · Zbl 1365.65302
[14] van de Geijn, R.A., Watts, J.: SUMMA: scalable universal matrix multiplication algorithm. Concurr. Comput. Pract. Exp. 9, 255-274 (1997)
[15] GNU. GNUMP library (2013). http://gmplib.org. Accessed 10 June 2013 · Zbl 0581.65031
[16] Grigori, L., Demmel, J., Xiang, H.: CALU: a communication optimal LU factorization algorithm. SIAM J. Matrix Anal. Appl. 32, 1317-1350 (2011) · Zbl 1242.65089
[17] Haidar, A., Ltaief, H., YarKhan, A., Dongarra, J.: Analysis of dynamically scheduled tile algorithms for dense linear algebra on multicore architectures. Concurr. Comput. Pract. Exp. 24, 305-321 (2011)
[18] Haque, S.A., Moreno Maza, M.: Determinant computation on the GPU using the condensation method. J. Phys. Conf. Ser. 341, 012031 (2012)
[19] van der Hoeven, J.: Ball arithmetic. In: Beckmann, A., Gaßner, C., Löwe, B. (eds.) Proceedings Logical approaches to Barriers in Computing and Complexity, pp. 179-208, Ernst-Moritz-Arndt-Universität Greifswald, Greifswald. http://www.texmacs.org/joris/ball/ball-abs.html
[20] van der Hoeven, J., Lecerf, G., Quintin, G.: Modular SIMD arithmetic in Mathemagix (2014). arXiv:1407.3383 · Zbl 1391.65003
[21] van der Hoeven, J., Lecerf, G., Mourain, B., et al.: Mathemagix, 2012-2014. Software. http://www.mathemagix.org. Accessed 15 Dec 2014
[22] INRIA. MPFI library. https://gforge.inria.fr/projects/mpfi/ (2013). Accessed 10 June 2013
[23] Johansson, F.: Arb (2013). http://fredrikj.net/arb/. Accessed 15 Dec 2014
[24] Kouya, T.: MPIGMP library (2013). http://na-inet.jp/na/. Accessed 10 June 2013
[25] Lu, M.: GPUprec: supporting high precision on graphics processors. http://code.google.com/p/gpuprec/ (2013). Accessed 10 June 2013
[26] von Mangoldt, H.: Zu Riemanns Abhandlung ‘Über die Anzhal der Primzahlen unter einer gegebenen Grösse’. J. Reine Agew. Math. 114, 255-305 (1985) · JFM 26.0215.03
[27] Matiyasevich, Yu.: A posteriori interval analysis. Lect. Notes Comput. Sci. 204, 328-334 (1985) · Zbl 0581.65031
[28] Matiyasevich, Yu.: New conjectures about zeroes of Riemann’s zeta function. Research report MA12-03 of the Department of Mathematics of the University of Leicester (2012). http://www2.le.ac.uk/departments/mathematics/research/research-reports-2/reports-2012/MA12_03Matiyasevich.pdf/view and from [32]. Accessed 15 Dec 2014
[29] Matiyasevich, Yu.: Calculating approximate values of zeros of Riemann’s zeta function via interpolating determinants. I. Funct. Anal. Other Math. 4(1) (2012) (to appear) · Zbl 0185.40101
[30] Matiyasevich, Yu.: Calculating approximate values of zeros of Riemann’s zeta function via interpolating determinants. II. Funct. Anal. Other Math. 4(2) (2012) (to appear)
[31] Matiyasevich, Yu.: Calculation of Riemann’s zeta function via interpolating determinants. Preprint 2013-18 of Max Planck Institute for Mathematics in Bonn (2013). http://www.mpim-bonn.mpg.de/preblob/5368 and from [32]. Accessed 15 Dec 2014
[32] Matiyasevich, Yu.: An artless method, ongoing project. http://logic.pdmi.ras.ru/ yumat/personaljournal/artlessmethod/. Accessed 15 Dec 2014
[33] Matiyasevich, Yu., Beliakov, G.: Zeroes of Riemann’s zeta function on the critical line with 20,000 decimal digits accuracy, Research Data Australia (2013). http://hdl.handle.net/10536/DRO/DU:30051725. Accessed 15 Dec 2014 · Zbl 0581.65031
[34] Nakayama, T.: CUMP library. http://www.hpcs.cs.tsukuba.ac.jp/ nakayama/cump/ (2013). Accessed 10 June 2013
[35] Nakayama, T., Takahashi, D.: Implementation of multiple-precision floating-point arithmetic library for GPU computing. In: Proceedings 23rd IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2011), pp. 343-349. IASTED Calgary, Canada (2011)
[36] Poulson, J., Marker, B., van de Geijn, R., Hammond, J., Romero, N.: Elemental: a new framework for distributed memory dense matrix computations. ACM Trans. Math. Softw. 39(2), 13:1-13:24 (2013) · Zbl 1295.65137
[37] Schönhage, A., Strassen, V.: Schnelle Multiplikation grosser Zahlen. Computing 7, 281-292 (1971) · Zbl 0223.68007
[38] Strassen, V.: Gaussian elimination is not optimal. Numer. Math. 13, 354-356 (1969) · Zbl 0185.40101
[39] Thakur, R., Rabenseifner, R., Gropp, W.: Optimization of collective communication operations in MPICH. Int. J. High Perform. Comput. Appl. 19, 49-66 (2005)
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.