FLINT3.7.0-dev
/

_gr_mat_charpoly_faddeev, gr_mat_charpoly_faddeev, _gr_mat_charpoly_faddeev_bsgs, gr_mat_charpoly_faddeev_bsgs

Synopsis#include <flint/gr_mat.h>
int _gr_mat_charpoly_faddeev(gr_ptr res, gr_mat_t adj, const gr_mat_t mat, gr_ctx_t ctx)source
int gr_mat_charpoly_faddeev(gr_poly_t res, gr_mat_t adj, const gr_mat_t mat, gr_ctx_t ctx)source
int _gr_mat_charpoly_faddeev_bsgs(gr_ptr res, gr_mat_t adj, const gr_mat_t mat, gr_ctx_t ctx)source
int gr_mat_charpoly_faddeev_bsgs(gr_poly_t res, gr_mat_t adj, const gr_mat_t mat, gr_ctx_t ctx)source

The characteristic polynomial by the Faddeev-LeVerrier algorithm [FadSom1972], which computes M_k = A M_{k-1} + c_{n-k+1} I and c_{n-k} = -\operatorname{tr}(A M_k) / k, and, if adj is not NULL, the adjugate matrix at no extra cost. The bsgs version is the baby-step giant-step variant of Preparata and Sarwate [PreSar1978], with O(n^{3.5}) operations instead of O(n^4) and \sqrt{n} temporary matrices. Both divide by 1, \ldots, n and fail (with GR_DOMAIN or GR_UNABLE) in small positive characteristic or without division.

References#

  • [FadSom1972] D. K. Faddeev and I. S. Sominsky. Problems in Higher Algebra. Mir Publishers, Moscow, 1972 (translated from the Russian edition of 1954). The method of Le Verrier and Faddeev for the characteristic polynomial.
  • [PreSar1978] F. P. Preparata and D. V. Sarwate. An improved parallel processor bound in fast matrix inversion. Information Processing Letters 7 (1978), 148–150. https://doi.org/10.1016/0020-0190(78)90079-0
Cite this page

The FLINT team, “_gr_mat_charpoly_faddeev, gr_mat_charpoly_faddeev, _gr_mat_charpoly_faddeev_bsgs, gr_mat_charpoly_faddeev_bsgs (gr_mat.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/gr_mat/_gr_mat_charpoly_faddeev.html (generated 2026-10-20).