Computing the Rank and a Small Nullspace Basis of a Polynomial Matrix

Details Computing the Rank and a Small Nullspace Basis of a Polynomial Matrix Computing the Rank and a Small Nullspace Basis of a Polynomial Matrix

2005-05-11

arxiv.org/abs/cs/0505030v1

Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation (2005) 309-316

Computer Science

Symbolic Computation

Research Report LIP RR2005-03, January 2005

Scientific paper

We reduce the problem of computing the rank and a nullspace 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)=softO(n^omega d) operations, with omega the exponent of matrix multiplication over K, then the algorithm uses softO(MM(n,d)) operations in K. The softO notation 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

Affiliated with

Also associated with

No associations

Rating

Computing the Rank and a Small Nullspace Basis of a Polynomial Matrix does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing the Rank and a Small Nullspace Basis of a Polynomial Matrix, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the Rank and a Small Nullspace Basis of a Polynomial Matrix will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-73296