论文标题
Faddeev-Leverrier算法和Pfaffian
The Faddeev-LeVerrier algorithm and the Pfaffian
论文作者
论文摘要
我们将FADDEEV-LEVERRIER算法适应了特征多项式的计算，以计算偏斜矩阵的Pfaffian。这产生了一种非常简单，易于实现的计算成本算法$ o（n^{β+1}）$，其中$ n $是矩阵的大小，$ o（n^β）$是乘以$ n \ times $ n \ times n $ n $ - matrices，$β\ in [2,2.37286）的成本。我们将其性能与其他算法的性能进行比较，并显示如何使用计算机代数来计算Riemannian歧管的Euler形式。
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 $O(n^{β+1})$ where $n$ is the size of the matrix and $O(n^β)$ is the cost of multiplying $n\times n$-matrices, $β\in[2,2.37286)$. 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.
