ISSN:
1432-0622
Keywords:
Rank
;
Hankel Matrix
;
Modular Methods
;
Rational Functions
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
,
Technology
Notes:
Abstract One of the main problems in the treatment of rational functions consists in representing them suitably for the purpose of their symbolic and algebraic manipulation. One can approach this problem by means of Hankel matrices if an efficient method for computing ranks is available. In this paper, a modular algorithm for determining the rank of a Hankel matrix with entries that are multivariate polynomials over the integers is presented. The algorithm is based on modular techniques, which consist in computing the rank of Hankel matrices over finite fields by a special algorithm that needsO(n2) arithmetic operations, wheren is the order of the matrix. The general solution is achieved by determining the maximum of the ranks computed over the finite fields. The worst case complexity of the algorithm isO(nr+3Gr+nr+2Gr+1) logn× log2 L, whereG andL are some appropriate bounds for the degree and the norm of the entries respectively.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01294834
Permalink
