# Workshop on Linear Computer Algebra and Symbolic-Numeric Computation

October 26 - 31, 2015, The Fields Institute

## 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 |
Overview of the recent progress on matrix multiplication
Francois Le Gall |

09:55 |
High performance dense linear algebra: arithmetic, algorithms and their parallelization
Clément Pernet, Université Grenoble-Alpes |

11:10 |
A Crash Course on Fast Interactive Proofs
Justin Thaler, Yahoo Labs |

13:45 to 14:40 |
Essentially Optimal Certificates in Linear Algebra
Jean-Guillaume Dumas, Université de Grenoble Alpes |

14:40 |
On rational functions without spurious poles
Bernhard Beckermann, Laboratoire Painlevé, Université de Lille |

16:00 |
Order bases, kernel bases and their use in fast polynomial matrix arithmetic
George Labahn |

09:00 to 09:55 |
The "Rheinfall" parallel algorithm for Gaussian Elimination
Riccardo Murri, Universität Zurich |

09:55 |
The Probability that Block Wiedemann Correctly Computes Invariant factors
Jeremy Johnson, Drexel University |

11:10 |
Quasideterminants, Degree Bounds and Algorithms for Matrices of Differential and Difference Polynomials
Mark Giesbrecht |

13:45 to 14:20 |
Symbolic-numeric computation of cutting planes for integer programming
Daniel Steffy, Oakland University |

14:20 |
Fast matrix rank algorithms and applications
Lap Chi Lau |

09:00 to 09:55 |
Solving Large Optimization Problems using Spectral Graph Theory
Gary Miller |

09:55 |
Fast computation of minimal interpolation bases with arbitrary weights
Vincent Neiger, LIP - ENS de Lyon |

11:10 |
Adaptive and generic parallel //computation of echelon forms
Ziad Sultan, laboratoire Jean Kuntzmann |

13:45 to 14:20 |
Exploring the Extended Linearization Algorithm (or XL Algorithm) for Solving Polynomial Systems of Equations, with Remarks toward NP-Completeness
Gregory Bard, University of Wisconsin---Stout |

14:20 |
Some recent techniques for faster linear algebra
Arne Storjohann |

09:00 to 09:55 |
Toward a numerical description of a complex affine scheme
Anton Leykin, Georgia Tech |

09:55 |
Sparse implicitization by interpolation matrices
Ioannis Emiris, University of Athens |

11:10 |
Issues in Blind Deconvolution via Computer Algebra (A Tale from the Dark Side)
Daniel Lichtblau, Wolfram Research |

13:45 to 14:40 |
SPECTRA: solving exactly linear matrix inequalities
Didier Henrion, CNRS |

14:40 |
Verified Solutions of Polynomial Systems
Nan Li, Tianjin University |

09:00 to 09:55 |
Birds and Frogs: polynomial and matrix questions from design theory
Ilias Kotsireas |

09:55 |
Optimal Backward Error and the Leaky Bucket
Rob Corless |

11:10 |
Bit complexity for quadratic minimization problems: the generic case
Mohab Safey El Din |

13:45 to 14:40 |
Error-correcting sparse interpolation of multivariate function
Zhengfeng Yang, East China Normal University |

14:40 |
Computing Approximate GCRDs of Differential Operators
Joseph Haraldson, University of Waterloo |

09:00 to 09:55 |
How sub-sampling leads to more robustness and higher resolution in digital signal processing
Wen-shin Lee, University of Antwerp |

09:55 |
On Recent Progress in Polynomial Root Finding
Michael Sagraloff, Max Planck Institute for Informatics |

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