Hybrid Methodologies for Symbolic-Numeric Computation

November 17, 2010 to November 19, 2010

Speakers and Abstrcts

• Hirokazu Anai, Fujitsu Laboratories Ltd. / Kyushu University, Japan
  • A symbolic-numeric approach to nonlinear dynamical system analysis
  • We consider to computer nonlinear gain functions for nonlinear dynamical systems which is one of the important tasks in dynamical system analysis. A numerical approach based on sum-of-squares for obtaining a nonlinear gain function has been proposed so far. However, there is no clue to find the minimum one. As a countermeasure against the issue, we discuss some symbolic-numeric procedures to analyze nonlinear gain functions of a class of dynamical systems by the combined use of sum-of-squares and quantifier elimination.
• Paola Boito, XLIM, University of Limoges, France
  • Decay properties of matrix functions: an application to electronic structure computation
  • Linear scaling methods, used in quantum chemistry and solid state physics for computation of electronic structures, rely on the phenomenon of localization: for certain choices of the basis functions, the Hamiltonian matrix that describes a physycal system is banded or sparse. The associated density matrix, which is a function of the Hamiltonian, is expected to exhibit an off-diagonal decay behavior, which may allow to replace the matrix with a banded approximation. Our goal is to give a rigorous mathematical description and proof of this property. By means of polynomial approximation and matrix analysis techniques, we formulate asymptotic bounds on the entries of the density matrix (as well as more general matrix functions). Such results allow to bound the error due to sparse/banded approximation.

    Applications of bounds for matrix functions are not limited to computational physics. The talk will present examples of how our approach can be used to estimate matrix functions that describe the connectivity properties of networks.

    This is joint work with Michele Benzi and Nader Razouk.

• Jürgen Gerhard, Maplesoft, Canada
  • Symbolic and symbolic-numeric techniques for dynamical modeling and simulation
  • Computer-aided mathematical modeling, analysis, and simulation of dynamical systems are playing a major role in today's engineering practice, notably for plant modeling, control design, calibration, and verification & validation. A variety of graphical tools for creating block diagrams of dynamical systems from first principles and from pre-built component libraries are in use today. Behind the scenes, the more modern ones amongst these tools create, simplify, and solve systems of differential-algebraic equations (DAEs), using a combination of purely symbolic, mixed symbolic-numeric, and purely numeric methods for preprocessing, simplification, and numerical integration.
    This talk will focus on a few aspects of dynamical equation simplification that have been investigated at Maplesoft since 2007 in a research project funded by Toyota:
    1. Differential elimination. Techniques for symbolic manipulation of partial differential equations (PDEs) have been researched for many years, with a view towards classification and symbolic solutions. In the context of engineering applications, the focus is different: DAEs instead of PDEs, large systems comprising thousands of (typically sparse) equations and variables, and the main goal of simplification is the ability to efficiently solve the system numerically. Our two main areas of consideration have been the reduction of the size of the equations, in order to reduce the computation time for function evaluation during numerical integration, and index reduction, where we developed a generalization of the so-called projection method, originally designed for mechanical systems, to arbitrary DAEs.
    2. Parameter space reduction. Once a DAE model of a dynamical system has been created, it may be required to identify or optimize the design parameters such as lengths, masses, resistances, capacities, etc. We have been researching a variety of symbolic and symbolic-numeric methods for reducing the number of design parameters in a DAE model and eliminating parameters that do not affect the dynamical behaviour in an essential way, employing techniques related to functional decomposition, sensitivity analysis, and dimensional analysis.
    3. Trajectory linearization. In engineering, there is an abundance of methods and techniques that were designed for and work well with linear dynamical systems. In practice, however, many systems exhibit significant nonlinear characteristics. A standard way of handling this situation is to consider a collection of local linear approximations, often called "modes", instead of a nonlinear model. This leads to the issue of finding a representative set of "operating points". We have studied symbolic-numeric algorithms that will choose the operating points along a specified "reference" trajectory, and then approximate the nonlinear behaviour by a piecewise or quasi-piecewise linear model. Applications include faster numerical simulation and control design.
       
• Roger Germundsson, Wolfram Research, USA
• Jonathan Hauenstein, Texas A&M University, USA
  • Deflation and isosingular sets
  • Deflation is a symbolic-numeric procedure which regularizes isolated solutions and irreducible components of a polynomial system. By incorporating the rank-deficiency methods of Bates, Hauenstein, Peterson, and Sommese into deflation, we can characterize how deflation will behave at non-isolated solutions, which leads to the concept of
    isosingular sets. This talk will describe this modified deflation process and isosingular sets as well as some of its applications in numerical algebraic geometry. This is joint work with Charles Wampler.
• Ilse Ipsen, North Carolina State University, USA
  • Panel Discussion
  • 1. What can symbolic methods do for ME? (They are slow and they use a lot of memory. Why bother?)
       Hybrid symbolic-numerical methods incorporate numerical algorithms to help with the solution of symbolic problems. How about numerical-symbolic methods, where symbolic algorithms help with the solution of numerical problems?
    2. When symbolic methods use "high precision" numerical methods (say Newton's method) in intermediate steps, how does one determine the precision for the numerical method?
       Do you take into account the condition number of the problem, and the numerical stability of the method? How do you decide how to measure conditioning: absolute, relative, normwise, which norm, componentwise,
       structured, etc? How many accurate digits do you want?
    3. Hybrid symbolic-numerical algorithms permit errors in the inputs (say from roundoff or physical measurements). What if the problem under consideration is illposed or illconditioned (say determination of rank, or a least squares problem with an illconditioned matrix or a large residual)? The input errors will be amplified, regardless of whether the arithmetic is exact or not. How does one determine the number of correct digits in the output?
    4. Is there anything that numerical analysts could contribute? Do the assumptions on which numerical methods are based fit the requirements of symbolic methods?
       Most numerical methods are designed for use in floating point arithmetic, which is characterized by relative perturbations. The accuracy is often measured by *normwise* relative perturbations, where the norms are chosen based on some analysis, discretization, or computational efficiency. Is that always appropriate for a symbolic computation?
       Do the numerical methods preserve the structure that is important for symbolic computations (say the backward error from computing the SVD of a Sylvester matrix is not again a Sylvester matrix)?
       The termination criterion for many iterative methods is a small backward error (say Krylov methods for linear systems, or Newton methods), and this backward error is often based on a (normwise) relative error bound. Is that accurate enough for symbolic computations?
• Kaori Nagatou, Kyushu University, Japan
  • Orbital stability investigations for travelling waves in a nonlinearly supported beam
  • For a nonlinear fourth-order beam equation with exponential nonlinearity, Breuer et al. proved that at least 36 travelling wave solutions exist for some specific wave speed [B. Breuer, J. Horak, P. J. McKenna, M. Plum, A computer-assisted existence and multiplicity proof for travelling waves in a nonlinearly supported beam, Journal of Differential Equations 224 (2006), pp. 60-97]. We investigate the orbital stability of these solutions by making use of both analytical and computer-assisted techniques.
• Michael Plum, Univeristät Karlsruhe, Germany
  • Computer-assisted existence and multiplicity proofs for elliptic boundary value problems
  • Many boundary value problems for semilinear elliptic partial differential equations allow very stable numerical computations of approximate solutions, but are still lacking analytical existence proofs. In this lecture, we propose a method which exploits the knowledge of a "good" numerical approximate solution, in order to provide a rigorous proof of existence of an exact solution close to the approximate one. This goal is achieved by a fixed-point argument which takes all numerical errors into account, and thus gives a proof which is not "worse" than any purely analytical one. The method is used to prove existence and multiplicity statements for some specific examples, including cases where purely analytical methods had not been successful.
• Greg Reid, University of Western Ontario, Canada
  • Geometric symbolic-numeric methods for differential and algebraic equation
  • In this talk I will describe progress in developing stable methods for approximate differential and algebraic systems. This progress will build on breakthroughs in the new area of numerical algebraic geometry. In that approach certain points, called witness points, are stably computed on the solution sets of polynomial equations. I will describe generalization of such methods to systems of overdetermined partial differential equations. In that case the points are witness points on the (jet) varieties of the equations.
• Mohab Safey El Din, Université Pierre et Marie Curie (Paris 6), France
  • On Applications of Quantifier Elimination to LMI and the Stability Region of Numerical Schemes
  • Quantifier elimination over the reals (QE) is a fundamental problem solved by Computer Algebra techniques. The effective resolution of QE problems can be first seen as a theoretical tool that may help to understand the intrinsic complexity of problems related to Linear Matrix Inequalities.

    The first part of this talk is a joint work with Lihong Zhi. We will show how one can use quantifier elimination to obtain an algorithm computing rational points in convex semi-algebraic sets iff such points exist. We will give upper bounds on the number of bit operations and the bit size of the returned points. As a by-product, we obtain upper bounds on the bit sie of rational solutions to Linear Matrix Inequalities (LMI) and sums-of-squares decompositions of multivariate polynomials over the rationals.

    We will exhibit the specific structure and properties of the considered QE problems. Such a structure and properties are shared by many other QE problems arising in applications, in particular for determining the stability region of numerical schemes. We will describe a dedicated QE algorithm that exploits these properties and its implementation. This algorithm is an extension/generalization of a Variant Quantifier Elimination algorithm previously obtained with Hoon Hong. Then, we will examine the complexity of this new special QE algorithm and illustrate its practical performances on examples that are out of reach of general QE solvers.

• Tanush Shaska, Oakland University, USA / University of Vlora, Albania
  • Numerical Methods in Algebraic Geometry
  • Most problems in algebraic geometry are difficult to solve using symbolic computation. However, a combination of numerical and symbolic computation can sometimes be successful. We will discuss such methods in computation of moduli spaces of covers and the field of invariants of binary octavics. Both problems have many applications in science and engineering.
• Mark Sofroniou, Wolfram Research, USA
  • Hybrid methods for Composition and Splitting
  • Decomposing a differential system into simpler subsystems often allows the construction of special purpose integration methods with advantageous numerical properties. The numerical integrator NDSolve in Mathematica provides a framework for implementing composition and splitting methods. Examples of some differential systems and appropriate numerical integrators will be given and details on the influence in the design of the solution framework will be given. Several composition methods be described along with some new schemes and details of the tools that have been used in their construction.
• Bernd Sturmfels, University of California, Berkeley, USA
  • Introduction to Convex Algebraic Geometry
  • Convex Algebraic Geometry is an emerging field at the interface of convex optimization and algebraic geometry. A primary focus lies on the mathematical underpinnings of semidefinite programming. This lecture offers a self-contained introduction. Starting with elementary questions concerning multifocal ellipses in the plane, we move on to discuss the geometry of spectrahedra and orbitopes, and we end with recent results on the convex hull of a real algebraic variety.
• Jan Verschelde, University of Ilinois at Chicago, USA
  • Quality Up in Polynomial Homotopy Continuation
  • Homotopy continuation methods to solve polynomial systems scale well on parallel computers, but their reliability and accuracy is often in doubt because of their reliance on floating-point arithmetic. In a recent joint work with Genady Yoffe we experimentally determined using QD-2.3.9 (a software library of Y. Hida, X.S. Li, and D.H. Bailey) that the overhead of double double arithmetic compared to working with ordinary doubles is of the same magnitude as computing with complex numbers. With multiple cores we can compensate for this overhead and thus achieve a so-called quality up. In particular, with 8 cores we can compute more accurately with double doubles in roughly the same time as in standard double precision. Similar factors apply to quadruple the working precision. This talk will address how the quad doubles of QD-2.3.9 are integrated and applied in the software package PHCpack to solve larger polynomial systems more accurately.
• Charles Wampler, General Motors, USA
  • Finding Exceptional Sets via Regenerative Fiber Products
  • For a parameterized family of polynomial systems, there may exist algebraic subsets of the parameter space above which the solution fibers have higher dimension than occurs in the surrounding region of parameter space. Such exceptional sets are often physically interesting. A case in point are so-called overconstrained mechanisms, which have more degrees of freedom of motion than expected. In 2008, Sommese and Wampler showed that taking fiber products over the parameter space promotes exceptional sets to become irreducible components, which makes them detectible by computing numerical irreducible
    decompositions of a sequence of fiber products. This talk will explore how the recent regeneration technique put forward by Hauenstein, Sommese, and Wampler can be applied to carry out these computations efficiently. While the core computation is based on numerical continuation, symbolics may play a role in preprocessing the system of equations, in deflating nonreduced algebraic sets that may arise in intermediate steps, and in reconstructing exact expressions for sets found numerically.
    

Early Career Speakers

• Dan Bates, Colorado State University, USA
  • Numerical consequences of symbolic choices in Gale Duality
  • A new method for solving systems of fewnomial equations relies on a symbolic transformation known as Gale duality followed by a numerical method called Khovanskii-Rolle continuation. While the computation of a Gale dual of a fewnomial system is rather straightforward, it is worthwhile to take care in choosing a ``good'' Gale dual, i.e., one that lends itself to efficient numerical solving. In this talk, we will review the procedures of Gale duality and Khovanskii-Rolle continuation recently produced by Frank Sottile and myself, followed by a discussion regarding the impacts of these symbolic choices in Gale duality on the efficiency of the entire procedure. This is joint work with J. Hauenstein, M. Niemerg, and F. Sottile.
• Sharon Hutton, North Carolina State University, USA
  • Computing the radius of positive semidefiniteness of a multivariate real polynomial via a dual of Seidenberg's method
  • We give a stability criterion for real polynomial inequalities with floating point or inexact scalars by estimating from below or computing the radius of semidefiniteness. That radius is the maximum deformation of the polynomial coefficient vector measured in a weighted Euclidean vector norm within which the inequality remains true. A large radius means that the inequalities may be considered numerically valid.

    The radius of positive (or negative) semidefiniteness is the distance to the nearest polynomial with a real root, which has been thoroughly studied before. We solve this problem by parameterized Lagrangian multipliers and Karush-Kuhn-Tucker conditions. Our algorithms can compute the radius for several simultaneous inequalities including possibly additional linear coefficient constraints. Our distance measure is the weighted Euclidean coefficient norm, but we also discuss several formulas for the weighted infinity and 1-norms.

    The computation of the nearest polynomial with a real root can be interpreted as a dual of Seidenberg's method that decides if a real hypersurface contains a real point. Sums-of-squares rational lower bound certificates for the radius of semidefiniteness provide a new approach to solving Seidenberg's problem, especially when the coefficients are numeric. They also offer a surprising alternative sum-of- squares proof for those polynomials that themselves cannot be represented by a polynomial sum-of-squares but that have a positive distance to the nearest indefinite polynomial.

    Joint Work With: Erich L. Kaltofen and Lihong Zhi
• Wen-shin Lee, University of Antwerp, Belgium
  • Searching for Sparsity
  • Lately, sparsity has become an important concept in signal and image processing. Smaller and smarter information process devices demand ever more sophisticated techniques to acquire and process data. Sparse methods are the key technology to meet the challenges in many applications.

    At the same time, research in sparse models and techniques has existed for decades. In computer algebra, sparse representations are developed and used to improve computational performance. Recent achievements in symbolic-numeric sparse interpolation allow both the input and outputs, with some added noise, represented in a finite precision environment.

    A connection to the associated structured matrices enables symbolic-numeric sparse interpolation algorithms to be generalized to a wider class of bases. We plan to discuss the corresponding issues in numerical linear algebra and investigate applications in identifying compact representations of biomedical signals.

• Anton Leykin, Georgia Institute of Technology, USA
  • Certified numerical homotopy tracking
  • Homotopy continuation is the numerical engine of hybrid symbolic-numerical algorithms with applications in the areas that require certification of the results. However, the step control mechanisms of the predictor-corrector methods commonly used for homotopy tracking do not give a guarantee of staying on a specified homotopy path. We have developed an algorithm that provides such guarantee in the rigorous sense of the alpha theory of Smale. (Joint work with Carlos Beltran)
• John May, Maplesoft, Canada
  • Applying Approximate Decomposition to Polynomial Root Finding
  • The problem of computing approximate (functional) decompositions of univariate polynomials is not as well studied as the approximate GCD and factorization problems, but it has an obvious application to polynomial root-finding. In this talk we will give an overview of known approximate decomposition techniques, and present some evidence to suggest that they can be useful in some root-finding applications.
• Andrew Novocin, ENS Lyon, France
  • Towards L1, a quasi-linear LLL
  • Numerical techniques have been applied to create floating-point versions of the famous LLL algorithm for lattice basis reduction. One such algorithm, the L^2 algorithm, has improved the algorithmic complexity, with respect to the bit-lengths of the input basis, from cubic to quadratic.
    Recent results on the numerical stability of LLL-reduced bases have paved the way for the analysis of a more aggressive attack. In this talk we present a new method and set of techniques for floating point lattice reductions. Our approach reduces gradually so that each step works on a basis which is itself merely a perturbation of a reduced basis. In such a context we can closely control the size of each operation.
• Philipp Rostalski, University of California, Berkeley, USA
  • Bermeja - Software for Convex Algebraic Geometry
  • Several great software tools in numerical algebraic geometry and optimization have been developed over the recent years, and in fact the inexperienced user might easily get lost in the variety of different tools, programming languages and input/output formats. Bermeja is a Matlab/Yalmip toolbox for computations in convex algebraic geometry which tries to overcome these obstacles by interfacing several existing tools as well as providing newly developed algorithms in a unifying modeling language. In this talk we will describe Bermeja and Yalmip and show how it can be used to solve optimization problems, compute roots or draw convex bodies. We finally share our vision of a powerful yet easy to use software toolbox for all kind of (numeric and symbolic-numeric) computations and invite everybody to foster its development.
• Damien Stehlé, École Normale Supérieure, Lyon, France
  • A numerically stable LLL reduction
  • Computations on Euclidean lattices arise in many fields of computer science and mathematics. The cornerstone of lattice algorithmics is the famous LLL reduction algorithm, which, despite being polynomial-time, remains somewhat slow. A natural means of speeding up an algorithm consists in working on an approximation of the input with smaller bit-size and showing that the work performed on the approximation is relevant for the actual exact input. Unfortunately, a lattice basis that is close to an LLL-reduced basis may not be itself LLL-reduced.
• Zhengfeng Yang, East China Normal University, China
  • Blind Image Deconvolution via Fast Approximate GCD
  • The problem of blind image deconvolution can be solved by computing approximate greatest common divisors (GCD) of polynomials. The bivariate polynomials corresponding to the z-transforms of several blurred images have an approximate GCD corresponding to the z-transform of the original image. Since blurring functions as cofactors have very low degree in general, this GCD will be of high degree. On the other hand, if we only have one blurred image and want to identify the original scene, the blurred image can be partitioned such that each part completely contains the blurring function, hence the blurring function becomes the GCD which is of low degree. Therefore, we design a specialized algorithm for computing GCDs of polynomials to recover true images in two different cases. The new algorithm is based on the fast GCD algorithm for univariate polynomials and the Fast Fourier Transform (FFT) algorithm. The complexity of our specialized algorithm for identifying both the true image and the blurring functions from blurred images of size n × n is O(n² log n) in the case of blurring functions of very low degree. The algorithm has been implemented in Maple and can extract true images of hundreds by hundreds pixel images from blurred images in a few seconds.
    
    

Please register through the MSRI Workshop web page. Registration is free, and would be appreciated prior to November 17, 2010.

View a List of Registered Participants

Organizers

• Erich Kaltofen (Organizing Chair), North Carolina State University, USA
• Mark Giesbrecht, University of Waterloo, Canada
• Daniel Lichtblau, Wolfram Research, USA
• Seth Sullivant, North Carolina State University, USA
• Lihong Zhi, Chinese Academy of Sciences, China

For more information, please email