A parallel algorithm for calculation of determinants and minors using arbitrary precision arithmetic

DOI10.1007/S10543-015-0547-ZzbMATH Open1338.65117arXiv1308.1536OpenAlexW1984863950MaRDI QIDQ285264FDOQ285264

Yu. Matiyasevich, Gleb Beliakov

Publication date: 19 May 2016

Published in: BIT (Search for Journal in Brave)

Abstract: We present a parallel algorithm for calculating very large determinants with arbitrary precision on computer clusters. This algorithm minimises data movements between the nodes and computes not only the determinant but also all minors corresponding to a particular row or column at a little extra cost, and also the determinants and minors of all submatrices in the top left corner 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. The algorithm was applied to studies of Riemann's zeta function.

Full work available at URL: https://arxiv.org/abs/1308.1536

Recommendations

• On computing the determinant in small parallel time using a small number of processors
• Parallel computation of determinants of matrices with polynomial entries
• The division free parallel algorithm for finding determinant
• Fast parallel algorithms for vandermonde determinants
• scientific article; zbMATH DE number 2187725
• scientific article; zbMATH DE number 1822266
• A fast parallel method for polynomial evaluation at points in arithmetic progressions
• A parallel algorithm for principal \(n\)th roots of matrices
• Parallelization of matrix algorithms for Gröbner basis computation

zbMATH Keywords

determinantnumerical exampleparallel algorithmsGPUill-conditioned matrixmessage passing interfaceRiemann's zeta function

Mathematics Subject Classification ID

Computation of special functions and constants, construction of tables (65D20) Parallel numerical computation (65Y05) (zeta (s)) and (L(s, chi)) (11M06) Numerical computation of determinants (65F40)

Cites Work

• Modular SIMD arithmetic in M <scp>athemagix</scp>
• CALU: A Communication Optimal LU Factorization Algorithm
• ScaLAPACK Users' Guide
• Communication-optimal parallel and sequential QR and LU factorizations
• Gaussian elimination is not optimal
• Fast multiplication of large numbers
• MPFR
• Matrix multiplication via arithmetic progressions
• Minimizing Communication in Numerical Linear Algebra
• Elemental
• Title not available (Why is that?)
• Approximation of Riemann’s Zeta Function by Finite Dirichlet Series: A Multiprecision Numerical Approach
• Proof of existence of global solutions form-component reaction–diffusion systems with mixed boundary conditions via the Lyapunov functional method
• The Riemann hypothesis. A resource for the afficionado and virtuoso alike

Cited In (7)

• Fast parallel algorithms for vandermonde determinants
• Plausible ways for calculating the Riemann zeta function via the Riemann-Siegel theta function
• Balanced incomplete factorization preconditioner with pivoting
• A review note on arbitrary precision arithmetic
• Riemann's zeta function and finite Dirichlet series
• COMPUTATION OF A DETERMINANT AND A MATRIX PRODUCT IN CELLULAR AUTOMATA
• A New Analysis of Iterative Refinement and Its Application to Accurate Solution of Ill-Conditioned Sparse Linear Systems

Uses Software

• gmp
• Mathemagix
• MPFI
• ScaLAPACK
• MPFR
• SUMMA
• CALU
• Elemental
• Arb
• MAGMA
• PLASMA
• MPIGMP
• GPUprec
• CUMP

This page was built for publication: A parallel algorithm for calculation of determinants and minors using arbitrary precision arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q285264)