PhD Public Lecture - Leili Rafiee Sevyeri (AP Math)
Zoom Link TBD
Title: Hybrid Symbolic-Numeric Computing in Linear and Polynomial Algebra
Abstract: We introduce hybrid symbolic-numeric methods which solve the approximate GCD problem for polynomials presented in Bernstein and Lagrange bases.
We adapt Victor Y. Pan’s root-based algorithm for finding approximate GCD to the case where the polynomials are expressed in Bernstein bases. We use the numerically stable companion pencil of Guðbjörn Jónsson to compute the roots, and the Hopcroft-Karp bipartite matching method to find the degree of the approximate GCD. We offer some refinements to improve the process.
We also introduce an algorithm with similar idea, which finds an approximate GCD for a pair of approximate polynomials given in a Lagrange basis. More precisely, we suppose that these polynomials are given by their approximate values at distinct known points. We first find each of their roots by using a Lagrange basis companion pencil for each polynomial. We introduce new clustering algorithms and use them to cluster the roots of each polynomial to identify multiple roots, and then marry the two polynomials using a Maximum Weight Matching algorithm, to find their GCD.