help annotate
Contents Next: Detecting periodicity Up: The computation of Previous: The basic algorithm

[Annotate][Shownotes]


An alternative approach, which avoids the computation of at each step, is to compute by using integer arithmetic. Let M be the companion matrix to , so that the eigenvalues of M are the conjugates of . If , as above, is such that , then the eigenvalues of are the conjugates of and the eigenvalues of are the conjugates of .

Now, has exactly two real conjugates corresponding to the two conjugates and of . Since for all k, it is easy to see that the conjugate of corresponding to is . Let us denote this conjugate by . For , has two real conjugates and itself. By definition, . Since all other conjugates are nonreal, the sign of the product of all conjugates is determined by that of , and thus

which is a compuation involving only finding the determinant of a finite number of matrices with integer entries. Note that the matrix is as good a representation of as is and can be computed from the recursion without explicitly computing the coefficients of . Of course, has integer entries rather than the d entries of the coefficient vector of .

Since the determinant computed above is just the resultant of and , another alternative is to use the coefficient vector of to represent and replace the determinant computation by the computation of a resultant at each step. Or, combining the approaches of § 5.1 and § 5.2, one could compute using floating point except in ``delicate'' cases. Experiments showed that the approach of § 5.2 was generally considerably slower than that of § 5.1.



help annotate
Contents Next: Detecting periodicity Up: The computation of Previous: The basic algorithm