Fields Institute Workshop on Hybrid Methodologies for Symbolic-Numeric Computation November 16-19, 2011 The University of Waterloo, Waterloo, Ontario, Canada

Hybrid 2011 – Talk titles and abstracts

Please click here for the main conference page.

Invited Speakers

• Laurent Bernardin, Maplesoft, Canada
  • Symbolic Computing in Modeling and Simulation
  • Modeling and Simulation of Physical Systems is a crucial topic in engineering, traditionally treated using numeric methods. It turns out that introducing symbolic computing techniques both expands the range of models that can be described and leads
    to significant speed gains in the numeric simulation phase. Using MapleSim as the
    example, we'll look at how combining numeric and symbolic techniques allows us to
    handle previously intractable models.
• Xiao-Wen Chang, School of Computer Science, McGill University
  • Lattice reduction and preconditioning (slides)
  • In this talk we will present our ongoing work on lattice reduction and preconditioning. First we present a floating-point block LLL reduction algorithm, which is rich in matrix-matrix multiplications. Then we present some lattice preconditioning strategies, which have a few applications. Numerical test results will be given to show effectiveness of our algorithms.
• Annie Cuyt, Universiteit Antwerpen (CMI), Belgium
  • Sparse interpolation and Signal processing
  • The breakthrough of compressed sensing in digital signal processing has created a real revolution. The fact that signals can be reconstructed with high probability from undersampled data opens up a whole new range of possibilities. A sparser model means higher compression, less data collection, storage or transmission, and a reduced model complexity.

    In coding theory [2] the reconstruction of a t-sparse object (i.e. represented by means of a linear combination containing only t elements) is achieved using only 2t samples, which is the absolute minimum. But it is widely believed, that a similar result does not hold in a noisy numeric environment [1, p. 28]. We show that by combining achievements in symbolic-numeric computing with results from numerical approximation theory, the numerical issues can be overcome. The new sparse technique, when applicable, is more efficient than compressed sensing.

    We take our illustrations from a biomedical application, the processing of EEG sig- nals. Current monitoring devices still transmit uncompressed EEG signals which is too power consuming in a wireless setup. Therefore acquisition and compression schemes are needed that require a smaller amount of data to represent the same biomedical information. This will resolve the power supply problem, which is mainly dominated by the amount of data being transmitted and the computationally expensive compression schemes.

    This is joint work with Wen-shin Lee.

    References:
    [1] E. J. Candés and M. B. Wakin. An introduction to compressive sampling. IEEE Signal Processing Magazine, 25(2):21–30, 2008.
    [2] J. L. Massey. Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory, 15(1):122–127, 1969.
• Maryam Fazel, University of Washington, USA
  • Strong Conditions for Recovering Low-rank Matrices
  • Recovering sparse vectors and low-rank matrices from noisy linear measurements has been the focus of much recent research. In this talk, we show how several classes of robust recovery conditions can be extended directly from vectors to matrices in a simple and transparent way, leading to the tightest known restricted isometry and nullspace conditions on the measurement map for matrix recovery. Results rely on the ability to ``vectorize" matrices through the use of a key singular value inequality. Based on joint work with Samet Oymak, Karthik Mohan, and Babak Hassibi.
• Wayne Hayes, University of California Irvine, USA
  • Shadowing as a measure of backward error in numerical simulations
  • Given a numerical solution Y to a system of equations E defining a dynamical system, we know that Y only approximately solves E. A "shadow" S of Y is defined to be an exact solution of E that starts close to Y and remains close for a long time. In other words, it is an exact solution to the dynamical system. Given the existence of a shadow, the numerical solution can be interpreted as an "observation" of an exact trajectory where the distance between the shadow and the numerical solution represents the "observational" error. I will review some concepts behind the idea of using shadowing as a measure of error of numerical solutions and dynamical systems and provide some examples of how I have used it to provide insight into the numerical reliability of simulations of physical systems.
• Hoon Hong, North Carolina State University, USA
  • Hybrid Method for Solving Bivariate Polynomial System
  • Many problems in science and engineering can be reduced to that of solving bivariate polynomial systems of equations. Intensive research efforts have yielded reliable symbolic methods and efficient numeric methods. We combine the advantages of symbolic methods (in particular resultant) and numeric methods (in particular Hansen-Sengupta operator with slope form). It seems that the resulting method reliably approximate all the solutions more efficiently than the other (symbolic, numeric) methods in most cases.
• Ken Jackson, University of Toronto, Canada
  • Validated Methods for Initial Value Problems for Ordinary Differential Equations (slides)
  • Compared to standard numerical methods for initial value problems (IVPs) for ordinary differential equations (ODEs), validated methods have two important advantages: if they return a solution to a problem, then
    1. the problem is guaranteed to have a unique solution, and
    2. an enclosure of the true solution is produced.

    We will survey validated methods for the numerical solution of IVPs for ODEs, describe several methods in a common framework, and identify areas for future research. If time permits, we will also discuss "shadowing", a form a backward error analysis that gives a computational proof that a numerical solution is near an exact solution to the ODE with a slightly perturbed initial condition

• David Jeffrey, University of Western Ontario, Canada
  • Stieltjes Integrals and Completely Monotonic Functions
  • Symbolic and numerical approaches to study the properties of the function f(x;a)=exp(a) - (1+a/x)^x. As a result of a combined approach, we obtain a new symbolic expression for the Stieltjes Transform of f(x;a) with respect to x, and bounds on the range of a for which the function is completely monotonic.
• Erich Kaltofen, North Carolina State University, USA
  • What is hybrid symbolic-numeric computation?
  • Hybrid symbolic-numeric computation constitutes the Fifth of my ``Seven Dwarfs'' of Symbolic Computation, which I have listed in my SNSC talk in Hagenberg in 2008. Hybridization requires that the solution of a computational mathematical problem should utilize both a numeric and a symbolic algorithmic component.

    In my talk, I will characterize the hybrid methodolgy by surveying some important results and the lessons I have learned from them. Those include the notion of approximate GCD and approximate sparse interpolant, and the analysis of the random distributions of matrix condition numbers in randomized hybrid algorithms.

    One can bypass the analysis by producing a certificate, and I will give sum-of-squares certificates in global optimization via our ArtinProver software. Specifically, I will discuss what constitutes an exact certificate on the case of the matrix rank.

    This work is in collaboration with Wen-shin Lee, Michael Nehring, B. David Saunders, Zhengfeng Yang, and Lihong Zhi.

• Wen-shin Lee, Universiteit Antwerpen (CMI), Belgium
  • Multivariate Prony's Method
  • In 1795, Gaspard Riche de Prony presented a method for interpolating a sum of exponential functions. Closely related to Pad ́e approximation, Prony’s method has found applications in the shape from moments problem, spectral analysis, and lately sparse sampling of signals with finite rate of innovation.

    On the one hand, the modern least squares approach of exponential modeling has evolved quite significantly from Prony’s original version. It yields additional insight into linear prediction algorithms for the autoregressive (AR) and autoregressive-moving average (ARMA) parameter estimation. On the other hand, the connection between Prony’s method and error-correcting codes has led to the development of symbolic-numeric sparse polynomial interpolation, which has already exploited a generalized eigenvalue reformulation and a link to Rutishauser’s qd-algorithm. This connection further enables a generalization of variances of Prony to other basis functions.

    Recall that a meromorphic function is a function analytic everywhere except at a set of isolated points that are called the poles of the function. Rutishauser’s qd-algorithm can determine the poles of a meromorphic function from its Taylor expansion. In the multivariate case such poles form a set of solutions of the associated multivariate polynomial equations. The interdependence between the Taylor expansion and poles becomes less obvious because there can be various ways to order the multivariate Taylor coefficients.

    Recent progress in the multivariate qd-algorithm expands our understanding in associating the convergence of multivariate poles to the different orderings of Taylor coefficients, among which a special case has been implemented in developing numerical multivariate polynomial factorization. Resorting to the link from qd to Padé leads us to a multivariate Prony’s method, which intricately involves higher-order tensors and their decompositions.

  • This is joint work with Annie Cuyt.

• Kosaku Nagasaka, Kobe University, Japan
  • A Symbolic-Numeric Approach to Gröbner Basis with Inexact Input (slides)
  • Computing a Gröbner basis or its variants for polynomials with inexact coefficients has been one of challenging problems in symbolic-numeric computations. In this talk, we review two methods: one is a direct approach using comprehensive Gröbner system and interval arithmetic and the other is structured Gröbner basis using Gaussian elimination and structured low rank approximation.
• Tateaki Sasaki, University of Tsukuba, Japan
  • Approximate Gröbner Bases and Two Applications
  • First, author's recent study on approximate Gröbner basis is surveyed. The approximate Gröbner basis is defined on two new concepts, "approximate ideal" and "accuracy-guarding reduction". Then, an algorithm for computing the approximate Gröbner bases is shown and basic properties of approximate Gröbner bases are explained. Second, as an application of approximate Gröbner bases, we consider detection of approximately singular systems and construction of related singular systems. Here, by "approximately singular system" Φ, we denote a multivariate polynomial system such that the dimension of variety(Φ) is increased by a small perturbation. We show a necessary condition for that the given system is approximately singular. Third, as another application, we consider polynomial systems which are ill-conditioned to solve numerically. We classify the ill-conditioned systems into 1) close-solution type (well known), 2) nearly singular type, 3) tiny leading-term type, and 4) other types. The first and the second types are characterized by Jacobian matrices, and the third type is characterized by the computation of approximate Gröbner bases. Finally, we give a simple method of well-conditioning for the systems of the second type.
• Adam Strzebonski, Wolfram Research, USA
  • Solving equations and inequalities using validated numeric methods (slides, Mathematica worksheet)
  • Validated numeric methods can be used to significantly speed up exact solving of equations and inequalities and to find and represent exact solutions of problems that cannot be solved by known purely symbolic algorithms. Mathematica solvers use such methods to find and represent roots of univariate polynomial and transcendental functions. The cylindrical algebraic decomposition algorithm, used to solve systems of real polynomial equations and inequalities, applies validated numeric methods in the lifting phase. In my talk I will discuss the types of validation of numeric computation results used by the Mathematica solvers. I will present the validation criteria used and describe the algorithms using them.
• Gilles Villard, CNRS & U. Lyon, France
  • Some numerical considerations for lattice basis reduction
  • Fastest algorithms and implementations for LLL basis reduction are highly hybrid symbolic-numeric. A "numerical engine" computes, via a orthogonalization process, the unimodular transformations that will improve the quality of the basis. Then, for example in the case of integer lattice bases, the transformations are applied in exact arithmetic.

    In this talk we will focus on several aspects concerning the choice of the precision than can be used for the numerical computations. We will present theoretical bounds based on reducedness perturbation results, and on a "fully numerical view" of the algorithms. We will see that this leads to new methods for certifying reducedness. We will also adopt a practical point of view for looking at approches with a dynamical tuning of the precision, and at the difficulties for heuristically mastering the behaviour of the codes when the precision is very low compared to theoretical requirements.

• Stephen Watt, University of Western Ontario, Canada
  • Approximate polynomials and definite integrals
  • We examine situations where approximate polynomials or polynomial-like objects appear in connection with definite integrals, such as initial value problems and fractional partial derivatives. This is exploratory work – no theorems will be presented.
• Hitoshi Yanami, Fujitsu Laboraties, Japan
  • A quantifier elimination algorithm based on symbolic-numeric cylindrical algebraic decomposition
  • These days quantifier elimination (QE) has been of great interest in many fields of science and engineering. We propose an effective QE algorithm based on cylindrical algebraic decomposition (CAD) combined with validated numerical methods. Our algorithm also includes a bounded CAD construction, which works for polynomial optimization problems we often encounter in engineering. The practicality of our implementation is examined by a number of experimental results.
    (Joint work with Hidenao Iwane, Hitoshi Yanami, and Hirokazu Anai)

Early Career Speakers

• Aurélien Greuet, SALSA Team (INRIA/CNRS/UPMC/LIP6) and Université de Versailles, France
  • Polar Varieties and Global Optimization Problem
  • Polar varieties are sets of polynomials defining critical points of a given polynomial map. Hence, they appear naturally in algebraic global optimization. In this talk, I will review some of their properties and show how they can be used (through numeric and symbolic computational approaches) to tackle difficult problems in global optimization:
    1. Ensuring the existence of sums-of-squares certificates of positivity to obtain lower bounds on a global infimum using semi-definite programming;
    2. Decide if a global infimum is a minimum using symbolic computation.

    This is joint work with F. Guo, M. Safey El Din and L. Zhi.

• Feng Guo, Chinese Academy of Sciences, Beijing, China and NC State University, USA
  • Certifying degree lower bounds for the Hilbert-Artin representation of positive semidefinite rational functions (slides)
  • In order to certify a given polynomial or rational function being nonnegative by its Hilbert-Artin representation, we need to fix the degree or the support set of its denominator. For a given degree or support set, if there does not exist such a representation, we give a rational certificate using Farkas Lemma for SDP. For a special case, we can certify a given polynomial being not SOS with our method. We also find the first polynomials which are nonnegative but can not be written as a ratio of sums of squares with the degree of denominator less than or equal to 2.
    
    This is joint work with Erich Kaltofen and Lihong Zhi.
• Bingyu Li, Northeast Normal University, Changchun, China
  • On the Condition Number of the Total Least Squares Problem (slides)
  • This talk concerns singular value decomposition (SVD)-based computable formulas and bounds for the condition number of the Total Least Squares (TLS) problem. For the TLS problem with the coefficient matrix A and the right-hand side b, a new closed formula is presented for the condition number. Unlike an important result in the literature that uses the SVDs of both A and [A, b], our formula only requires the SVD of [A, b]. Based on the closed formula, both lower and upper bounds for the condition number are derived. It is proved that they are always sharp and estimate the condition number accurately. A few lower and upper bounds are further established that involve at most the smallest two singular values of A and of [A, b]. Tightness of these bounds is discussed, and numerical experiments are presented to confirm our theory and to demonstrate the improvement of our upper bounds over the upper bound due to Golub and Van Loan. Such lower and upper bounds are particularly useful for large scale TLS problems since they require the computation of only a few singular values of A and of [A, b] other than all the singular values of them.
• Daniel S. Roche, US Naval Academy, USA
  • Stable Sparse Interpolation with Fewer Samples (slides)
  • Given noisy samples of a high-degree polynomial with few nonzero terms, we consider the problem of recovering the (exact) exponents and (approximate) coefficients of the unknown polynomial. This problem of approximate sparse interpolation has received considerable attention over the last decade from a range of areas. There is a connection to recent work on compressed sensing in the signal processing community, and applications within symbolic-numeric computing include nonlinear system solving as well as approximate factorization.

    Our ongoing work is aimed at developing algorithms which achieve high, provable numeric stability while also requiring as few samples as possible from the unknown sparse polynomial, in terms of its degree and the number of nonzero terms. We will present progress towards an optimal algorithm for the approximate sparse interpolation problem, where the number of samples matches an information-theoretic lower bound and the algorithm is stable in the sense of forward error.

    This is joint work with Mark Giesbrecht

• Olivier Ruatta, Université de Limoges, France
  • On two different problems and methods for approximate GCD
  • In this talk, we will introduce two problems of computing an approximate greatest common divisor. The first one is the classical problem and we present an iterative method based on Weierstrass iteration for overconstrained systems of algebraic equations and the second one concern the case where one of the input polynomial is known almost exactly or more accurately than the other and we propose a method based on companion matrices. Each time, we reduce the problem to an optimization problem. In fact this approach (transform an algebraic problem to an optimization one) in order to treat approximated or numerical algebraic problem is one of the main systematic tool of symbolic-numeric computation. We will see that the two proposed algorithms, even if they seem different are in fact closely related through this approach.
• Dan Steffy, Zuse Institute Berlin, Germany and Oakland University, USA
  • Exact solutions to mixed-integer linear programming problems (slides)
  • We present a hybrid symbolic-numeric algorithm for solving mixed-integer linear programming problems exactly over the rational numbers. By performing many operations with floating-point arithmetic and then verifying and correcting results using symbolic computation, exact solutions can be found without relying entirely on rational arithmetic. In particular, we study the performance of several safe dual bounding methods which can be used in place of an exact linear programming solver for many computations. Computational results will be presented based on an implementation within the constraint integer programming framework SCIP. Includes joint work with Bill Cook, Thorsten Koch and Kati Wolter.
• Katya Vladislavleva, Evolved Analytics, Belgium
  • Symbolic regression for modeling complex continuous and discrete- continuous systems
  • Symbolic regression is a mature methodology for model identification and variable selection from real world data. In this talk we introduce the main principles of symbolic regression and the additional algorithmic improvements that are necessary to make symbolic regression suitable for practical problem solving. Besides generating robust and transparent nonlinear models on possibly unbalanced data with missing and correlated inputs, symbolic regression workflows can now be used to efficiently identify driving variables, outliers in data, and provide robust response predictions using ensembles of diverse models. We illustrate these capabilities on industrial examples from various fields.
• Min Wu, East China Normal University, Shanghai, China
  • Exact Safety Verification of Hybrid Systems via Symbolic-Numeric Method
  • As a common mathematical model for complex physical systems, hybrid systems are dynamical systems governed by interacting discrete and continuous dynamics. In this talk we present a work on safety verification of hybrid systems, i.e., deciding whether a given system can enter into some unsafe regions in the state space.

    A symbolic-numeric algorithm is proposed to compute inequality invariants of the given systems, by transforming this problem into a parameterized polynomial optimization problem. We first obtain the candidates of numerical inequality invariants by polynomial Sum-of-Squares (SOS) relaxation via Semidefinite Programming (SDP), and then apply the Gauss-Newton refinement and rational vector recovery techniques to recover polynomials with rational coefficients that satisfy exactly the conditions of invariants.

Tutorials

• Anton Leykin, Georgia Tech, USA
  • Numerical Algebraic Geometry (slides)
  • One of the basic problems arising in many pure and applied areas of mathematics is to solve a system of polynomial equations. Numerical Algebraic Geometry (NAG) starts with addressing this fundamental problem and develops machinery to describe higher-dimensional solution sets (varieties) with approximate data. Numerical polynomial homotopy continuation, NAG's main engine, is radically different from the classical symbolic approaches, since it is powered by (inexact) numerical methods. Beyond the very basic routines the methods of NAG are truly hybrid: for instance, symbolic and numerical techniques are combined to treat singular solutions and verify decompositions of varieties.
• Steve Vavasis, University of Waterloo, Canada
  • Condition numbers in the solution of polynomial equations (slides)
  • Condition numbers play a major role in the analysis of problems posed over the real and complex numbers and in the development of real-number algorithms. The tutorial will start by characterizing the concept of condition number. Then condition numbers for classic problems including square linear systems, linear least squares, eigenvalues and linear programming will be reviewed. Finally, the last part of the tutorial will cover condition numbers for solving polynomial equations in one or more variables.

Tutorials will be appropriate for graduate students and researchers looking to explore some conference themes in depth.

Program and Schedule

The conference will be held in room DC1302 on the main floor of the William G. Davis Centre. Registration, breaks, and reception will be in DC 1301, or the "fishbowl", the big glass-enclosed room on the main floor. See below for directions to the conference site.

The program will be comprised of tutorials, invited senior speakers, invited early career speakers. There will also be time and opportunity
for interaction and collaboration.