Symbolic/Numeric Hybrid Algorithms
Computer algebra offers a strong tool for the scientists to
carry out the often expensive algebraic computations in
mathematical models of scientific theories. But just like
any other theory, it has limitation. There are problems for
which the computation of an exact symoblic solution is
prohibitively expensive; there are other problems for which
no exact symbolic solution is known; and there are problems
with inexact data. It is now becoming more and more clear that
symbolic and numeric computation can be done together,
combining the speed and low memory usage of numeric
computation with the mathematical veracity of symbolic
computation. While some work in this field had already
begun in the 1980s, recently activities have been
growing in depth and breadth. We focus on several areas
of symbolic-numeric algebra for polynomials.
Symbolic-Numeric Method for Solving Polynomial System
With Greg Reid (University of Western Ontario, Canada), we exploited the well-known correspondence between polynomial systems and systems of constant coefficient linear homogeneous PDE and presented a new criterion of involution and a stable algorithm for solving zero-dimensional polynomial systems. The method was applied to determine the position and orientation of an internally calibrated camera from known 3D reference points and their images. The method combined with the moment method can give an efficient way to find all real solutions of polynomial systems.
With Xiaoli Wu (my Ph.D student), we presented a method based on symbolic-numeric reduction to geometric involutive form to compute the primary component and the differential operators for an isolated singular solution of a polynomial system.
If the singular solution was known with limited accuracy, then we performed generalized Newton iterations to refine it to high accuracy quickly (accuracy doubles with each new iteration).
With Nan Li (my Ph.D student),
we proposed a novel method based on the regularized
Newton iteration and the computation of differential conditions satisfied at the approximate singular
solution for
refining approximate singular solutions to the full machine
precision. Our algorithm converges
quadratically and the size of matrices involved in our algorithm is bounded by the number of variables. By introducing well-chosen smoothing parameters to the given system,
we proposed firstly a verification method for computing verified and narrow error bounds, such that a
slightly perturbed system is proved to possess a singular root within computed error
bounds. We demonstrated the performance of the algorithm
for polynomial systems with singular solutions of multiplicity up to hundreds.
Approximate Polynomial GCD Computation and Factorization
With Rob Corless and Stephen Watt (University of Western Ontario, Canada), we used QR factors of the Sylvester matrix to compute the greatest common divisor (GCD) of univariate polynomials. The algorithm is now distributed as the function QRGCD in the SNAP package of Maple. I also designed fast GCD algorithms based on displacement structure of the Sylvester matrix and the Bezout matrix . The cost of the algorithms is quadratic in the degrees of the given polynomials. With Erich Kaltofen (North Carolina State University, USA) and Zhengfeng Yang, we presented a GCD algorithm based on the structured total least squares method and demonstrated on a diverse set of benchmark polynomials that the algorithm in practice computes globally minimal approximations. As an application of the linearly constrained approximate GCD problem, we presented an STLS-based method that computes a real or complex polynomial the nearest real or complex polynomial that has a root of multiplicity at least k. We demonstrated that the algorithm in practice computes on the benchmark polynomials given in the literature the known globally optimal nearest singular polynomials.
With Zijia Li and Zhengfeng Yang (my Ph.D students), we presented a specialized GCD algorithm for computing approximate GCDs of univariate or bivariate polynomials arising from blind images deconvolution problem. To recover images from the blurred ones of size n*n, we are able to reduce the complexity to
O(n^2 log(n)) in the case of blurring functions of very low degree.
Together with Shuhong Gao (Clemson University£¬USA), Erich Kaltofen, John May (Kaltofen¡¯s Ph. D student), Zhengfeng Yang, we made use of the SVD of the Ruppert matrix to determine the number of factors and approximate nullspace vectors. The approximate factors were extracted by our new approximate polynomial GCD algorithm based on the STLS of the generalized Sylvester matrices. We successfully found the approximate factors of four examples arise in the engineering of Stewart-Gough platforms. The paper at the 2004 ISSAC received the ACM SIGSAM Distinguished Student Author Award.
With Kaltofen, May, Yang, we generalized the differential forms introduced by Ruppert to many variables, and used structured total least squares (STLS) approximation and Gauss-Newton optimization to numerically compute the approximate multivariate factors. The new algorithm efficiently yields approximate factorizations of a large set of benchmark polynomials within the coefficient noise even when the relative error in the input is substantial.
Polynomial Global Optimization and Certified Solutions
Together with Kaltofen, Yang and Li,
we converted the imprecise and possibly invalid SOS certificate into an exact SOS certificate with exact rational scalars and polynomials vie Newton iterations, rational vector reconstructions and projections. Our algorithms successfully certify accurate rational lower bounds near the irrational global optima for for benchmark approximate polynomial greatest common divisors and multivariate polynomial irreducibility radii from the literature, and factor coefficient bounds in the setting of a model problem posted by Siegfried Rump (Hamburg University of Technology, Germany). With Kaltofen and Feng Guo (my Ph.D student), we extended impossibility certificates to Hilbert-Artin representations of a given denominator degree. Our algorithm can compute certificates of impossibilities for an arbitrary sum-of-squares denominator of degree 2 and 4 for some symmetric sextics in 4 and 5 variables, respectively.
With Mohab Safey El Din (University Paris 6), Aurelien Greuet (Safey El Din's Ph. D student) and Feng Guo, we show that the lower bounds of the infimum of a polynomial with or without constrains can be computed by sums of squares of polynomials over the union of the modified polar varieties. Our algorithm does not require that the infimum is attainable. In
addition, our method adds fewer polynomial constraints of lower degree.
With Safey El Din, we design the first algorithm deciding if a convex semi-algebraic set contains a rational point and computes such a point if it exists. The analysis of its bit-complexity gives bounds on the height of rationals appearing in an SOS decomposition of a multivariate polynomial. Furthermore, with Safey El Din and Qingdong Guo (my Ph.D student), we provide an algorithm which decides the existence of rational solutions to the linear matrix inequality. This leads to best complexity bounds for deciding the existence of rational sums of squares of polynomials. The algorithm provides the first computer
validation of Scheiderer¡¯s counter-example to Sturmfels¡¯ question (a multivariate polynomial that is a sum of squares over the reals but not over the rationals). The paper at the 2013 ISSAC received the ACM SIGSAM Distinguished Student Author Award.
With Zhengfeng Yang and Yijun Zhu (Yang's Ph.D student), we introduce algorithms for verifying the
existence of real solutions of positive-dimensional polynomial
systems. The verification algorithm combined with the low-rank
moment matrix completion method proposed by me and Yue Ma (my Ph.D student) can also be used to verify the existence of at least one real root of a semialgebraic system.
Return to Zhi's Home