# Workshop on Linear Computer Algebra and Symbolic-Numeric Computation

**Location: ** Fields Institute, Room 230

## Overview

This workshop explores explores the interactions between two classical areas in symbolic and numeric computation.

#### Algorithms for Symbolic Linear Algebra

While constituting a classical researchfield in mathematical computing, algorithms for linear algebra problems is still very much a current, vibrant and highly applicable research topic. Research into exact, symbolic, and numeric methods with floating point arithmetic is deeply intertwined, in part because the manipulation of sparse matrices or the location of errors in the inputs can involve discrete combinatorial approaches. Our vision for the workshop foresees focus on several current research topics:

- The computational complexity of linear algebra problems is classical, as the matrix multiplication complexity remains open. However, new important recent results on the problem for multiplication [Le Gall, Williams] and essentially linear time algorithms for Laplacians of graphs [Lau, Miller, Peng, Spielman, Yuster] and certification of the outputs [Dumas, Kaltofen, Thaler] form a day's topic of our workshop.
- Errors in inputs have received attention as large data sets require clean-upbefore solving: outlier-sensitive least squares fitting [Ipsen, Mahoney] and removal of incorrect constraints [Candes] and points in interpolation problems [Kaltofen, Yang] form the subject of a half-day.
- Diophantine linear algebra is a rich area of current research, including lattice basis reduction algorithms [Stehle], Hermite and Smith normal forms [Giesbrecht, Storjohann] and discrete optimization [Cook]. We dedicate a half-day of our workshop to diophantine methods.
- Exact algorithms for dense and sparse linear algebra and linear programming problems, over exactfields and rings, are the back-bone of symbolic computation software. Two days are dedicated to symbolic algorithms [Albrecht, Bard, Dumas, Giorgi, Labahn, Murri, Steffy, Pernet, Sultan, Vialla]. We shall account for new results discovered in this rich area of research between now and the program, and we plan to add a new topic and speakers to our workshop accordingly.

### Symbolic-Numeric Computation

Algorithms that combine techniques from symbolic and numeric computation have been of increasing importance and interest over the past decade. The necessity to work reliably with imprecise and noisy data, and for speed and accuracy within algebraic and hybrid-numerical problems, has encouraged new interactions between the numerical and symbolic computing fields. An example of a typical problem is that of approximate polynomial system solving: given a set of polynomials that have no common real or complex root, deform the scalars in the polynomials minimally to have common roots. For two univariate polynomials the problem specializes to the approximate GCD problem. For linear polynomials the problem is total least squares fitting.

Problems such as those have imported ideas from numerical analysis into computer algebra and have had applications in numerous areas from motion planning to image deblurring. Current topics include certified solution of polynomial systems, optimizing functions over varieties, numerical system solving with parametric entries, nearest polynomials with given properties, as well as improved algorithms for earlier problems such as approximate polynomial gcd, factorization, sparse interpolation, etc. The goal of this workshop is to support the interaction and integration of symbolic and numeric computing. Several international workshops have been organized in this area in recent years, including the Fields Institute Workshop on Hybrid Methodologies for Symbolic-Numeric Computation (Waterloo, Canada, November 2011) and most recently SNC 2014 held as a satellite meeting of the ICM.

## Schedule

09:00 to 09:55 |
Francois Le Gall |

09:55 |
Clément Pernet, Université Grenoble-Alpes |

11:10 |
Justin Thaler, Yahoo Labs |

13:45 to 14:40 |
Jean-Guillaume Dumas, Université de Grenoble Alpes |

14:40 |
Bernhard Beckermann, Laboratoire Painlevé, Université de Lille |

16:00 |
George Labahn |

09:00 to 09:55 |
Riccardo Murri, Universität Zurich |

09:55 |
Jeremy Johnson, Drexel University |

11:10 |
Mark Giesbrecht |

13:45 to 14:20 |
Daniel Steffy, Oakland University |

14:20 |
Lap Chi Lau |

09:00 to 09:55 |
Gary Miller |

09:55 |
Vincent Neiger, LIP - ENS de Lyon |

11:10 |
Ziad Sultan, laboratoire Jean Kuntzmann |

13:45 to 14:20 |
Gregory Bard, University of Wisconsin---Stout |

14:20 |
Arne Storjohann |

09:00 to 09:55 |
Anton Leykin, Georgia Tech |

09:55 |
Ioannis Emiris, University of Athens |

11:10 |
Daniel Lichtblau, Wolfram Research |

13:45 to 14:40 |
Didier Henrion, CNRS |

14:40 |
Nan Li, Tianjin University |

09:00 to 09:55 |
Ilias Kotsireas |

09:55 |
Rob Corless |

11:10 |
Mohab Safey El Din |

13:45 to 14:40 |
Zhengfeng Yang, East China Normal University |

14:40 |
Joseph Haraldson, University of Waterloo |

09:00 to 09:55 |
Wen-shin Lee, University of Antwerp |

09:55 |
Michael Sagraloff, Max Planck Institute for Informatics |

11:10 |
Daniel Roche, U.S. Naval Academy |