Efficient algorithms for computing the characteristic polynomial in a domain

DOI10.1016/S0022-4049(99)00158-9MaRDI QIDQ5928850zbMATH OpenWikidataFDO

Authors Jounaïdi Abdeljaoued, Gennadi I. Malaschonok

Publication date 3 July 2001

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0022-4049(99)00158-9

zbMATH Keywords

algorithmcharacteristic polynomialDodgson eliminationfree finite rank-a modulenumerical examplesQT matrixSylvester determinant identity

Mathematics Subject Classification ID

Free, projective, and flat modules and ideals in associative algebras (16D40) Endomorphism rings; matrix rings (16S50) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Review text

New sequential methods are given for computing the characteristic polynomial of an endomorphism of a free finite rank-a module over a domain, that require \(O(n^3)\) ring operations with exact division. The Dodgson elimination process is analysed as a sequence of matrices by using Sylvester determinant identity. The Dodgson process is applied for reducing a given square matrix to a similar QT matrix. The algorithm is ilustrated on a numerical example.

Recommendations

• Computation of the characteristic polynomial of an endomorphism of a free module
• Faster algorithms for the characteristic polynomial
• Efficient computation of the characteristic polynomial
• Calculation of the characteristic polynomial of a matrix
• Deterministic computation of the characteristic polynomial in the time of matrix multiplication

Cites work

• An improved parallel processor bound in fast matrix inversion
• Computational methods of linear algebra
• Efficient Gaussian Elimination Method for Symbolic Determinants and Linear Systems
• Fast Parallel Matrix Inversion Algorithms
• scientific article; zbMATH DE number 435565 (Why is no real title available?)
• scientific article; zbMATH DE number 4208276 (Why is no real title available?)
• scientific article; zbMATH DE number 3949600 (Why is no real title available?)
• Solution of a system of linear equations in an integral ring
• Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
• Various proofs of Sylvester's (determinant) identity.

Cited in

(8)

• Fast algorithms for the characteristic polynomial
• Deterministic computation of the characteristic polynomial in the time of matrix multiplication
• An algorithmic characterization of polynomial functions over \(\mathbb Z_{p^n}\)
• COMPUTATIONALLY EFFICIENT RECURSIONS FOR TOP-ORDER INVARIANT POLYNOMIALS WITH APPLICATIONS
• scientific article; zbMATH DE number 16648 (Why is no real title available?)
• Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets
• Elimination for Coefficients of Special Characteristic Polynomials
• Effective lower bounds on the matrix rank and their applications

This page was built for publication: Efficient algorithms for computing the characteristic polynomial in a domain

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