PhD Seminar • Symbolic Computation — A Survey on the Polynomial Approximate Greatest Common Divisor ProblemExport this event to calendar

Monday, June 17, 2019 2:00 PM EDT

Joseph Haraldson, PhD candidate
David R. Cheriton School of Computer Science

The polynomial Approximate Greatest Common Divisor (GCD) problem consists of given two polynomials, find a pair of nearby polynomials having a non-trivial GCD. This talk discusses the problem of how to approximate an exact GCD numerically to arbitrarily high precision and optimization approaches to compute nearby polynomials with a non-trivial GCD.

Classical approximate GCD techniques rely on the singular value decomposition and QR factorization, which are generally suitable for initial guesses to optimization routines. The existence and uniqueness of solutions to the problem is reviewed and presented in the context of optimization algorithms based on gradient and Newton methods. A large portion of the talk discusses the polynomial time algorithm of Karmarkar and Lakshman that is able to solve the simplest variant of the approximate GCD problem using variable projection.

Location 
DC - William G. Davis Computer Research Centre
1304
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
  1. 2024 (100)
    1. April (23)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)