Name
Abstract | ||
|---|---|---|
We reduce the problem of computing the rank and a null-space basis of a univariate polynomial matrix to polynomial matrix multiplication. For an input n x n matrix of degree, d over a field K we give a rank and nullspace algorithm using about the same number of operations as for multiplying two matrices of dimension, n and degree, d. If the latter multiplication is done in MM(n,d)= O~(nωd operations, with ω the exponent of matrix multiplication over K, then the algorithm uses O~MM(n,d) operations in, K. For m x n matrices of rank r and degree d, the cost expression is O(nmr ω-2d). The soft-O notation O~ indicates some missing logarithmic factors. The method is randomized with Las Vegas certification. We achieve our results in part through a combination of matrix Hensel high-order lifting and matrix minimal fraction reconstruction, and through the computation of minimal or small degree vectors in the nullspace seen as a K[x]-module. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1145/1073884.1073927 | international symposium on symbolic and algebraic computation |
Keywords | DocType | Volume |
small nullspace basis,univariate polynomial matrix,nullspace basis,n matrix,matrix rank,rank r,input n,minimal polynomial basis,latter multiplication,field k,polynomial matrix,linear algebra,matrix multiplication,matrix minimal fraction reconstruction,nullspace algorithm,small degree vector,minimal polynomial | Conference | abs/cs/0505030 |
ISSN | ISBN | Citations |
Proceedings of the 2005 International Symposium on Symbolic and
Algebraic Computation (2005) 309-316 | 1-59593-095-7 | 19 |
PageRank | References | Authors |
1.25 | 20 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arne Storjohann | 1 | 391 | 33.19 |
| Gilles Villard | 2 | 565 | 48.04 |