The Faddeev-LeVerrier algorithm and the Pfaffian

DOI10.1016/J.LAA.2021.07.023MaRDI QIDQ820990zbMATH OpenOpenAlexFDO

Authors Christian Bär

Publication date 29 September 2021

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

determinantcharacteristic polynomialPfaffianGauss-Bonnet-Chern theorem

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Numerical computation of determinants (65F40)

Abstract: We adapt the Faddeev-LeVerrier algorithm for the computation of characteristic polynomials to the computation of the Pfaffian of a skew-symmetric matrix. This yields a very simple, easy to implement and parallelize algorithm of computational cost $$ where $n$ is the size of the matrix and $$ is the cost of multiplying $nimesn$-matrices, $$. We compare its performance to that of other algorithms and show how it can be used to compute the Euler form of a Riemannian manifold using computer algebra.

Recommendations

• Numeric and symbolic evaluation of the Pfaffian of general skew-symmetric matrices
• A factorization algorithm to compute Pfaffians
• Algorithm 923: Efficient numerical computation of the Pfaffian for dense and banded skew-symmetric matrices
• On the computation of pfaffians
• Faster combinatorial algorithms for determinant and Pfaffian

Cites work

• scientific article; zbMATH DE number 3125713 (Why is no real title available?)
• scientific article; zbMATH DE number 3516529 (Why is no real title available?)
• scientific article; zbMATH DE number 1235881 (Why is no real title available?)
• scientific article; zbMATH DE number 1775055 (Why is no real title available?)
• scientific article; zbMATH DE number 3184480 (Why is no real title available?)
• A modified Leverrier-Faddeev algorithm for matrices with multiple eigenvalues
• A new extension of Leverrier's algorithm
• A simple intrinsic proof of the Gauss-Bonnet formula for closed Riemannian manifolds
• Algorithm 923: Efficient numerical computation of the Pfaffian for dense and banded skew-symmetric matrices
• An improved parallel processor bound in fast matrix inversion
• Classroom Note:A Simple Proof of the Leverrier--Faddeev Characteristic Polynomial Algorithm
• Computing the Lambert \(W\) function in arbitrary-precision complex interval arithmetic
• Further limitations of the known approaches for matrix multiplication
• Gaussian elimination is not optimal
• Leverrier’s Algorithm: A New Proof and Extensions
• Numeric and symbolic evaluation of the Pfaffian of general skew-symmetric matrices
• On Faddeev-Leverrier's method for the computation of the characteristic polynomial of a matrix and of eigenvectors
• On computing the determinant in small parallel time using a small number of processors
• On the modified Leverrier-Faddeev algorithm
• Partial and Total Matrix Multiplication
• Powers of tensors and fast matrix multiplication
• The combinatorial approach yields an NC algorithm for computing Pfaffians

Cited in

(8)

• Optimized implementation for calculation and fast-update of Pfaffians installed to the open-source fermionic variational solver mVMC
• Algorithm 923: Efficient numerical computation of the Pfaffian for dense and banded skew-symmetric matrices
• A note on the Le Verrier-Fadeev's method
• , , AND REINHARDT’S PROGRAM
• scientific article; zbMATH DE number 5015711 (Why is no real title available?)
• Numeric and symbolic evaluation of the Pfaffian of general skew-symmetric matrices
• Characteristic polynomials in Clifford algebras and in more general algebras
• A factorization algorithm to compute Pfaffians

Describes a project that uses

Uses Software

• SageMath
• Pfaffian
• Algorithm 923

This page was built for publication: The Faddeev-LeVerrier algorithm and the Pfaffian

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