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

DOI10.1007/S10543-015-0547-ZMaRDI QIDQ285264zbMATH OpenOpenAlexFDO

Authors Gleb Beliakov, Yu. Matiyasevich

Publication date 19 May 2016

Published in BIT (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3930239 (Why is no real title available?)
• Approximation of Riemann's zeta function by finite Dirichlet series: a multiprecision numerical approach
• CALU: A communication optimal LU factorization algorithm
• Communication-optimal parallel and sequential QR and LU factorizations
• Elemental, a new framework for distributed memory dense matrix computations
• Fast multiplication of large numbers
• Gaussian elimination is not optimal
• MPFR
• Matrix multiplication via arithmetic progressions
• Minimizing communication in numerical linear algebra
• Modular SIMD arithmetic in \textsc{Mathemagix}
• Proof of existence of global solutions form-component reaction–diffusion systems with mixed boundary conditions via the Lyapunov functional method
• ScaLAPACK Users' Guide
• The Riemann hypothesis. A resource for the afficionado and virtuoso alike

Cited in

(8)

• 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
• Computation of a determinant and a matrix product in cellular automata
• A review note on arbitrary precision arithmetic
• A new analysis of iterative refinement and its application to accurate solution of ill-conditioned sparse linear systems
• Riemann's zeta function and finite Dirichlet series
• The division free parallel algorithm for finding determinant

Describes a project that uses

Uses Software

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

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)