PE is a ?s-weak Popov basis of K(F) ,
, We first prove that the number of rows of PE is the rank of K(F), that is, k = m ? rank(F)
m} \ {? 1 + · · · + ? j , 1 ? j ? m} sorted in increasing order. Since P is the submatrix of the rows of Q whose ?s-pivot index is not in this set, P has k = r ? (m ? m) = m ? rank(F) rows. Now, by construction, P is in ?s-weak Popov form and its ?s-pivot index has entries in {? 1 + · · · + ? i , 1 ? i ? m}. Thus we can apply Lemma 5.7; it ensures that PE is in ?s-weak Popov form and that rdeg ?s (PE) = rdeg ?s (P). It remains to prove that PE is a basis of K(F), Item (iv) of Lemma 5.9, the ?s-pivot index of the ?s-Popov basis of K(EF) contains the ?s-pivot index of S. By Lemma 5.8, the latter is the tuple formed by the integers in the set {1 ,
Since P (resp. K) is the submatrix of the rows of Q (resp. B) whose ?s-pivot index is in {? 1 + · · · + ? j , 1 ? j ? m}, and since both P and K are in ?s-weak Popov form, it follows that P and K have the same ?s-pivot profile. In particular, we have rdeg ?s (P) = rdeg ?s (K) = d, from which we get rdeg ?s (PE) = d. According to Lemma 2.3, since the rows of PE are in K(F), this implies that PE is a basis of K(F). 6: Apply Definition 5.12 to (?, EF, ? + 1) to obtain the order L ?+1 (?) ? Z n+n >0 and the matrix L ? ,
?) ? Z m+n ?0 ,
,
?)?L ?+1 (?) use uniform order ,
Step 4: Deduce first ?s-weak Popov basis of K(EF), then ?s-weak, m+n)×(m+n) ? PM-Basis, vol.11 ,
P ? K[x] k×m ? the rows of Q whose ?s-pivot index is in {? 1 + · · · + ? j , 1 ? j ? m} 14: return PE Proposition 5.14. Algorithm 4 is correct. Let D = max(|s|, |cdeg s (F)|, 1). Then, assuming m ? n and using notation from the algorithm, its cost is bounded by the sum of: ? the cost of performing PM-Basis at order at most 2 D/m + 2 on an input matrix of row dimension m + n ?, ? first m columns of the rows of M which have nonpositive ?t-degree, vol.13 ,
, Using the assumption that ?s-reduced bases of K(F) have ?s-row degree 0 along with Item (iv) of Lemma 5.9 shows that the ?s-reduced bases of K(EF) have ?s-row degree 0. Thus, we can apply Lemma 5.13 to (EF, s, µ, ?) with µ = ? + 1 > max(s) and ? = cdeg s (EF) + 1, which is ? = cdeg s (F) + 1 according to Item (i) of Lemma 5.9
Efficient algorithms for computing the characteristic polynomial in a domain, Journal of Pure and Applied Algebra, vol.156, pp.127-145, 2001. ,
The complexity of partial derivatives, Theoretical computer science, vol.22, pp.317-330, 1983. ,
A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matrix Anal. Appl, vol.15, pp.804-823, 1994. ,
Shifted normal forms of polynomial matrices, ISSAC'99, ACM, pp.189-196, 1999. ,
Normal forms for general polynomial matrices, J. Symbolic Comput, vol.41, pp.708-737, 2006. ,
URL : https://hal.archives-ouvertes.fr/hal-02101933
On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, vol.18, pp.147-150, 1984. ,
Triangular factorization and inversion by fast matrix multiplication, Mathematics of Computation, vol.28, pp.231-236, 1974. ,
Algebraic Complexity Theory, 1997. ,
On fast multiplication of polynomials over arbitrary algebras, Acta Inform, vol.28, pp.693-701, 1991. ,
On the minimum computation time of functions, 1966. ,
Fast parallel matrix inversion algorithms, 16th Annual Symposium on Foundations of Computer Science (sfcs 1975), pp.11-12, 1975. ,
The numerical solution of the secular equation, Matem. Sbornik, vol.44, pp.169-171, 1937. ,
Fast computation of the rank profile matrix and the generalized Bruhat decomposition, J. Symbolic Comput, vol.83, pp.187-210, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01251223
Efficient computation of the characteristic polynomial, ISSAC'05, ACM, pp.140-147, 2005. ,
URL : https://hal.archives-ouvertes.fr/hal-00004056
Abstract Algebra, 2004. ,
Collected Problems in Higher Algebra, Problem n979, 1949. ,
Minimal Bases of Rational Vector Spaces, with Applications to Multivariable Linear Systems, SIAM Journal on Control, vol.13, pp.493-520, 1975. ,
A simple recurrent formula for inverting a matrix (abstract), Bull. of Amer. Math. Soc, vol.55, 1045. ,
, Modern Computer Algebra, 2013.
Nearly optimal algorithms for canonical matrix forms, SIAM Journal on Computing, vol.24, pp.948-969, 1995. ,
On the complexity of polynomial matrix computations, ISSAC'03, ACM, pp.135-142, 2003. ,
URL : https://hal.archives-ouvertes.fr/hal-02101878
Certification of minimal approximant bases, ISSAC'18, ACM, pp.167-174, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01701861
Triangular x-basis decompositions and derandomization of linear algebra algorithms over, 2012. ,
, J. Symbolic Comput, vol.47, pp.422-453
Faster polynomial multiplication over finite fields, J. ACM, vol.63, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-02350386
A generalization of the fast LUP matrix decomposition algorithm and applications, Journal of Algorithms, vol.3, pp.45-56, 1982. ,
Fast computation of minimal interpolation bases in Popov form for arbitrary shifts, pp.295-302, 2016. ,
URL : https://hal.archives-ouvertes.fr/hal-01265983
Computing minimal interpolation bases, J. Symbolic Comput, vol.83, pp.272-314, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01241781
Fast computation of approximant bases in canonical form, J. Symbolic Comput, vol.98, pp.192-224, 2020. ,
URL : https://hal.archives-ouvertes.fr/hal-01683632
Linear Systems, 1980. ,
On the complexity of computing determinants, Computational Complexity, vol.13, 2005. ,
URL : https://hal.archives-ouvertes.fr/hal-02102099
Fast algorithms for the characteristic polynomial, Theoretical Computer Science, vol.36, pp.309-317, 1985. ,
Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix, J. Complexity, vol.42, pp.44-71, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01345627
Powers of tensors and fast matrix multiplication, pp.296-303, 2014. ,
Sur les variations séculaires deséléments elliptiques des sept plantètes principales, Journal des Mathématiques Pures et Appliquées, vol.5, pp.220-254, 1840. ,
Bruhat canonical form for linear systems, Linear Algebra Appl, vol.425, pp.261-282, 2007. ,
On lattice reduction for polynomial matrices, J. Symbolic Comput, vol.35, pp.139-145, 2003. ,
Computing Popov and Hermite Forms of Rectangular Polynomial Matrices, pp.295-302, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01701867
Computing canonical bases of modules of univariate relations, ISSAC'17, ACM, pp.357-364, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01457979
Faster Algorithms for the Characteristic Polynomial, ISSAC'07, ACM, pp.307-314, 2007. ,
Invariant description of linear, time-invariant controllable systems, SIAM Journal on Control, vol.10, pp.252-264, 1972. ,
A method of determining explicitly the coefficients of the characteristic equation, Annals of Mathematical Statistics, vol.13, pp.424-429, 1942. ,
Normalization of row reduced matrices, ISSAC'11, ACM, pp.297-304, 2011. ,
Une méthode pour la décomposition spectrale et l'inversion des matrices, Comptes-Rendus de l'Académie des Sciences, vol.227, pp.1010-1011, 1948. ,
High-order lifting and integrality certification, J. Symbolic Comput, vol.36, p.97, 2003. ,
Notes on computing minimal approximant bases, Challenges in Symbolic Computation Software, 2006. ,
Gaussian elimination is not optimal, Numer. Math, vol.13, pp.354-356, 1969. ,
FFLAS-FFPACK: Finite Field Linear Algebra Subroutines / Package, 2019. ,
, Linbox: Linear algebra over black-box matrices, 2019.
The complexity of a scheme of functional elements realizing the multiplication of integers, Soviet Mathematics Doklady, vol.3, pp.714-716, 1963. ,
A general module theoretic framework for vector M-Padé and matrix rational interpolation, Numer. Algorithms, vol.3, pp.451-462, 1992. ,
Linear Multivariable Systems, Applied Mathematical Sciences, vol.11, 1974. ,
Fast Order Basis and Kernel Basis Computation and Related Problems, 2012. ,
Efficient computation of order bases, ISSAC'09, ACM, pp.375-382, 2009. ,
Efficient algorithms for order basis computation, J. Symbolic Comput, vol.47, pp.793-819, 2012. ,
Computing column bases of polynomial matrices, ISSAC'13, ACM, pp.379-386, 2013. ,
Unimodular completion of polynomial matrices, ISSAC'14, ACM, pp.413-420, 2014. ,
Computing minimal nullspace bases, ISSAC'12, ACM, pp.366-373, 2012. ,
, If K is in ?s-Popov form, then K is in ?s-Popov form
m}, we rely on the definition of a leading matrix (see Section 2.3): the entry (i, j) of , then the entry (i, j) of lm ?s (K) is equal to L i,? . This holds, since in this case we have s j = ? ? , and by construction of K the ,? , which itself is equal to L i,? by definition of a leading matrix. Now assume K is in ?s-Popov form ,
, using further notation from Section 5.2: S is the basis of K(E) described in Lemma 5.8 and B = [ K S ] ? K[x] (k+m?m)×m is the basis of K(EF) given in Eq, Now we prove the claims in Remark 5.10 concerning variants of Item (iv) of Lemma 5.9
With the above notation and assumptions, ? If K is in ?s-reduced form, then B is in ?s-reduced form. ? If K is in ?s-Popov form, then B is in ?s-Popov form up to row permutation ,