Faster combinatorial algorithms for determinant and Pfaffian

DOI10.1007/S00453-008-9240-9MaRDI QIDQ848938zbMATH OpenOpenAlexFDO

Authors Anna Urbańska

Publication date 23 February 2010

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-008-9240-9

zbMATH Keywords

algorithmcombinatoricsdeterminantgraphmatrixPfaffian

Mathematics Subject Classification ID

Numerical computation of determinants (65F40)

Review text

The author describes a novel algebraic view of the algorithms of \textit{M. Mahajan} and \textit{V. Vinay} [in: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (1997); Chic. J. Theor. Comput. Sci. 1997, Article No.~5 (1997; Zbl 0924.68088)] for computing the determinant and Pfaffian of skew-symmetric matrices. This is based on a relation to a pseudo-polynomial dynamic-programming algorithm for the knapsack problem, which gives to the authors the possibility to interpret the Mahajan-Vinay algorithm as a computation of an algebraic version of this problem.

Recommendations

• Faster Combinatorial Algorithms for Determinant and Pfaffian
• scientific article; zbMATH DE number 1775055
• scientific article; zbMATH DE number 1332669
• On the computation of pfaffians
• The combinatorial approach yields an NC algorithm for computing Pfaffians

Cites work

• A combinatorial approach to matrix algebra
• A combinatorial proof of the Cayley-Hamilton theorem
• Advanced determinant calculus
• Determinant: Old Algorithms, New Insights
• scientific article; zbMATH DE number 3957110 (Why is no real title available?)
• scientific article; zbMATH DE number 176871 (Why is no real title available?)
• scientific article; zbMATH DE number 3461412 (Why is no real title available?)
• scientific article; zbMATH DE number 1332669 (Why is no real title available?)
• scientific article; zbMATH DE number 1151367 (Why is no real title available?)
• scientific article; zbMATH DE number 1775055 (Why is no real title available?)
• scientific article; zbMATH DE number 1405680 (Why is no real title available?)
• scientific article; zbMATH DE number 3312627 (Why is no real title available?)
• Matching theory
• Matrix multiplication via arithmetic progressions
• Overlapping Pfaffians
• Rectangular matrix multiplication revisited
• The complexity of computing the permanent
• The complexity of partial derivatives

Cited in

(12)

• On the computation of pfaffians
• A fast algorithm for index of annihilation computations
• The combinatorial approach yields an NC algorithm for computing Pfaffians
• A factorization algorithm to compute Pfaffians
• Faster geometric algorithms via dynamic determinant computation
• Computation of principal \({\mathcal A}\)-determinants through dimer dynamics
• Computing Puiseux-Series Solutions to Determinantal Equations via Combinatorial Relaxation
• scientific article; zbMATH DE number 1332669 (Why is no real title available?)
• scientific article; zbMATH DE number 1775055 (Why is no real title available?)
• Fast parallel algorithms for vandermonde determinants
• Faster Combinatorial Algorithms for Determinant and Pfaffian
• The Faddeev-LeVerrier algorithm and the Pfaffian

This page was built for publication: Faster combinatorial algorithms for determinant and Pfaffian

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