University of Waterloo COVID-19 update

Please see the University of Waterloo’s frequently asked questions for information about COVID-19 and how it has affected university operations.

Please visit the list of modified services if you have questions about university services.

Although the University of Waterloo is closed for in-person events until further notice, many virtual events and presentations of interest to computer scientists are taking place each week at the Cheriton School of Computer Science. Please check out what our students and faculty are doing.

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
26
27
28
29
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
4
5
6
  1. 2020 (107)
    1. June (6)
    2. May (17)
    3. April (20)
    4. March (17)
    5. February (25)
    6. January (22)
  2. 2019 (255)
    1. December (21)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (220)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)