University Of Lethbridge.pdf

On January 30, 2004, Howard Cheng presented a talk focusing on polynomial Greatest Common Divisor (GCD) computation within the Department of Mathematics & Computer Science at the University of Lethbridge. The discussion centered around a fundamental operation in computer algebra, crucial for tasks like rational function simplification, polynomial factorization, and integration.

While the Euclidean algorithm is a well-known method for GCD calculation, it can lead to significant "intermediate expression swell," causing intermediate results to grow even with small input and output sizes. Cheng offered a linear algebra perspective to address this issue, demonstrating how this approach aids in managing coefficient growth.

The talk covered several classical techniques:

1. Primitive Euclidean Algorithm: A standard method for GCD calculation.
2. Subresultant Algorithm: Involves computing subresultants to determine the GCD.
3. Modular Algorithm: Uses modular arithmetic to streamline the process.

Cheng concluded with a recent advancement in the modular algorithm, promising that the first part of the talk, focusing on linear algebra fundamentals, should be accessible to those who have completed an introductory course in the subject. The presentation was a collaboration between Howard Cheng and George Labahn from the University of Waterloo.