Faster combinatorial algorithms for determinant and Pfaffian
type: Item
instance of: scholarly article
title: Faster combinatorial algorithms for determinant and Pfaffian
zbMATH Open document ID: 1193.65049
author: Anna Urbańska
published in: Algorithmica
publication date: 2010-02-23T00:00:00Z
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.
reviewed by: Constantin Popa
Mathematics Subject Classification ID: 65F40
zbMATH DE Number: 5674319
zbMATH Keywords: algorithm
zbMATH Keywords: determinant
zbMATH Keywords: combinatorics
zbMATH Keywords: graph
zbMATH Keywords: matrix
zbMATH Keywords: Pfaffian
MaRDI profile type: Publication
full work available at URL: s00453-008-9240-9
OpenAlex ID: W1505415134
cites work: Matching theory
cites work: Advanced determinant calculus
cites work: Q4047029
cites work: Q4259990
cites work: The complexity of partial derivatives
cites work: Q4542181
cites work: Q4389326
cites work: Q3726126
cites work: Q5593031
cites work: A combinatorial proof of the Cayley-Hamilton theorem
cites work: A combinatorial approach to matrix algebra
cites work: Q4036702
cites work: Determinant: Old Algorithms, New Insights
cites work: Matrix multiplication via arithmetic progressions
cites work: Rectangular matrix multiplication revisited
cites work: The complexity of computing the permanent
cites work: Overlapping Pfaffians
cites work: Q4938661
DOI: 10.1007/S00453-008-9240-9
description: scientific article; zbMATH DE number 5674319