References

In exact computing environments such as Maple and Mathematica problems often have symbolic parameters. As such a typical domain for computation is an integral domain (such as Q[a1,..., ak]) rather than a field. In such environments growth of coefficients in intermediate computations are a central concern. For methods that involve elimination intermediate growth can be controlled by removing greatest common divisors at each step. Fraction-free computation is an elimination process which controls coefficient growth in intermediate computations while at the same time avoids expensive greatest common divi-sor computations. In this talk we give a new, fast algorithm for solving the simultaneous Pade ́ approxi-mation problem. The algorithm is fraction-free and is intended for computation in exact arithmetic. The algorithm gives significant improvement on previous fraction-free meth-ods, in particular when solved via the use of vector Hermite-Pade ́ approximation using the FFFG order basis algorithm previously done by the authors. The improvements are both in terms of bit complexity and in reduced size of the intermediate quantities. The primary technique takes advantage of certain duality properties of Hermite-Pade ́ and Simultaneous-Pade ́ approximation problems