Symbolic Computation of Conserved Densities for Systems of Nonlinear Evolution Equations

A new algorithm for the symbolic computation of polynomial conserved densities for systems of nonlinear evolution equations is presented. The algorithm is implemented inMathematica. The programcondens.mautomatically carries out the lengthy symbolic computations for the construction of conserved densities. The code is tested on several well-known partial differential equations from soliton theory. For systems with parameters,condens.mcan be used to determine the conditions on these parameters so that a sequence of conserved densities might exist. The existence of a large number of conservation laws is a predictor for integrability of the system.     

A recursive algorithm for coprime fractions and Diophantineequations

The computation of coprime fractions for proper rational matrices and the solving of the minimal design problem are important in the design of multivariable systems by using polynomial fractional terms. A recursive algorithm, which fully exploits the shift-invariant property of the generalized resultants, is developed to carry out these computations. A method for solving the Diophantine equation that is based on this algorithm is outlined. This results in a significant reduction in computation as compared to the standard methods involving solution of linear algebraic equations. Some comparisons to existing methods show that the present algorithm is computationally more attractive with regard to efficiency and accuracy     

Computing infeasibility certificates for combinatorial problems through Hilbert’s Nullstellensatz

Systems of polynomial equations with coefficients over a field K can be used to concisely model combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over the algebraic closure of the field K. In this paper, we investigate an algorithm aimed at proving combinatorial infeasibility based on the observed low degree of Hilbert’s Nullstellensatz certificates for polynomial systems arising in combinatorics, and based on fast large-scale linear-algebra computations over K. We also describe several mathematical ideas for optimizing our algorithm, such as using alternative forms of the Nullstellensatz for computation, adding carefully constructed polynomials to our system, branching and exploiting symmetry. We report on experiments based on the problem of proving the non-3-colorability of graphs. We successfully solved graph instances with almost two thousand nodes and tens of thousands of edges.     

Computing stable poses of piecewise smooth objects

When a three dimensional object is known to be lying on a planar surface, its pose is restricted from six to three degrees of freedom. Computer vision algorithms can exploit the few stable poses of modeled objects to simplify scene interpretation and more accurately determine object location. This paper presents necessary and sufficient conditions for the pose of a piecewise smooth curved three-dimensional object to be stable. For objects whose surfaces are represented by implicit algebraic equations, these conditions can be expressed as systems of polynomial equations that are readily solved by homotopy continuation. Examples from the implemented algorithm are presented.     

A hybrid parallel solver for systems of multivariate polynomials using CPUs and GPUs

This paper deals with a problem of finding valid solutions to systems of polynomial constraints. Although there have been several quite successful algorithms based on domain subdivision to resolve this problem, some major issues are still demanding further research. Prime obstacles in developing an efficient subdivision-based polynomial constraint solver are the exhaustive, although hierarchical, search of the zero-set in the parameter domain, which is computationally demanding, and their scalability in terms of the number of variables. In this paper, we present a hybrid parallel algorithm for solving systems of multivariate constraints by exploiting both the CPU and the GPU multicore architectures. We dedicate the CPU for the traversal of the subdivision tree and the GPU for the multivariate polynomial subdivision. By decomposing the constraint solving technique into two different components, hierarchy traversal and polynomial subdivision, each of which is more suitable to CPUs and GPUs, respectively, our solver can fully exploit the availability of hybrid, multicore architectures of CPUs and GPUs. Furthermore, our GPU-based subdivision method takes advantage of the inherent parallelism in the multivariate polynomial subdivision. We demonstrate the efficacy and scalability of the proposed parallel solver through several examples in geometric applications, including Hausdorff distance queries, contact point computations, surface–surface intersections, ray trap constructions, and bisector surface computations. In our experiments, the proposed parallel method achieves up to two orders of magnitude improvement in performance compared to the state-of-the-art subdivision-based CPU solver.     

Parametric optimization and optimal control using algebraic geometry methods

We present two algebraic methods to solve the parametric optimization problem that arises in non-linear model predictive control. We consider constrained discrete-time polynomial systems and the corresponding constrained finite-time optimal control problem. The first method is based on cylindrical algebraic decomposition. The second uses Gröbner bases and the eigenvalue method for solving systems of polynomial equations. Both methods aim at moving most of the computational burden associated with the optimization problem off-line, by pre-computing certain algebraic objects. Then, an on-line algorithm uses this pre-computed information to obtain the solution of the original optimization problem in real time fast and efficiently. Introductory material is provided as appropriate and the algorithms are accompanied by illustrative examples.     

Fast and highly scalable parallel computations for fundamental matrix problems on distributed memory systems

We present fast and highly scalable parallel computations for a number of important and fundamental matrix problems on distributed memory systems (DMS). These problems include matrix multiplication, matrix chain product, and computing the powers, the inverse, the characteristic polynomial, the determinant, the rank, the Krylov matrix, and an LU- and a QR-factorization of a matrix, and solving linear systems of equations. Our highly scalable parallel computations for these problems are based on a highly scalable implementation of the fastest sequential matrix multiplication algorithm on DMS. We show that compared with the best known parallel time complexities on parallel random access machines (PRAM), the most powerful but unrealistic shared memory model of parallel computing, our parallel matrix computations achieve the same speeds on distributed memory parallel computers (DMPC), and have an extra polylog factor in the time complexities on DMS with hypercubic networks. Furthermore, our parallel matrix computations are fully scalable on DMPC and highly scalable over a wide range of system size on DMS with hypercubic networks. Such fast (in terms of parallel time complexity) and highly scalable (in terms of our definition of scalability) parallel matrix computations were rarely seen before on any distributed memory systems.     

Fast interference detection between geometric models

We present efficient algorithms for interference detection between geometric models described by linear or curved boundaries and undergoing rigid motion. The set of models include surfaces described by rational spline patches or piecewise algebraic functions. In contrast to previous approaches, we first describe an efficient algorithm for interference detection between convex polytopes using coherence and local features. Then an extension using hierarchical representation to concave polytopes is presented. We apply these algorithms along with properties of input models, local and global algebraic methods for solving polynomial equations, and the geometric formulation of the problem to devise efficient algorithms for convex and nonconvex curved objects. Finally, a scheduling scheme to reduce the frequency of interference detection in large environments is described. These algorithms have been successfully implemented and we discuss their performance in various environments.     

一种基于几何性质的鱼眼图像校正算法

为快速、高效地校正具有径向畸变的鱼眼图像,提出一种基于几何性质的校正算法。根据投影不变性原理以及径向畸变的几何特性,计算畸变直线的斜率,并通过求解线性方程组得出多项式校正模型的参数。实验结果表明,该算法能够以较低的运算复杂度获得较高的校正精度,相比于采用数学迭代拟合直线的方法,该算法在图像整体校正质量上有明显改善。     

Minimal realization of a differential system

There are many algorithms for deriving a state variable model for a system defined by a matrix transfer function. It is shown how these algorithms may be applied to the derivation of state variable models for systems defined by linear constant differential equations. without the use of polynomial computations.     

Implementation of the FGLM Algorithm and Finding Roots of Polynomial Involutive Systems

In this paper, an implementation of the FGLM algorithm that transforms Gröbner bases from one ordering to another is presented. Some additional optimizations that considerably expedite computations are considered. It is shown that this algorithm can be used for finding roots of polynomial systems represented in the involutive form.     

Multiple parallel computations of terms of generalized polynomial forms of representations of Boolean functions

Methods for vector and multiple logical computations are described. An algorithm is presented that allows for parallel computations of the values of the conjunctive terms of generalized polynomial forms using multiple sets of variables. Evaluations of the performance of the proposed algorithm are given. An example of multiple parallel computations of the terms of an arithmetic polynomial is analyzed.     

New approach to analysis and optimal control of time-varying systems via Taylor series

A new approach with three novel operations is proposed to deal with analysis of linear and bilinear time-varying systems and optimal control of linear time-varying systems via the Taylor series. The use of the three operations: polynomial mapping, general multiplication and integral transformer can greatly simplify the algorithm derivations and computations. Recursive algorithms are obtained and several illustrative examples are given.     

Analysis of nonlinear electrical circuits using bernstein polynomials

In electrical circuit analysis, it is often necessary to find the set of all direct current (d.c.) operating points (either voltages or currents) of nonlinear circuits. In general, these nonlinear equations are often represented as polynomial systems. In this paper, we address the problem of finding the solutions of nonlinear electrical circuits, which are modeled as systems of n polynomial equations contained in an n-dimensional box. Branch and Bound algorithms based on interval methods can give guaranteed enclosures for the solution. However, because of repeated evaluations of the function values, these methods tend to become slower. Branch and Bound algorithm based on Bernstein coefficients can be used to solve the systems of polynomial equations. This avoids the repeated evaluation of function values, but maintains more or less the same number of iterations as that of interval branch and bound methods. We propose an algorithm for obtaining the solution of polynomial systems, which includes a pruning step using Bernstein Krawczyk operator and a Bernstein Coefficient Contraction algorithm to obtain Bernstein coefficients of the new domain. We solved three circuit analysis problems using our proposed algorithm. We compared the performance of our proposed algorithm with INTLAB based solver and found that our proposed algorithm is more efficient and fast.     

Liouvillian solutions of third order differential equations

The Kovacic algorithm and its improvements give explicit formulae for the Liouvillian solutions of second order linear differential equations. Algorithms for third order differential equations also exist, but the tools they use are more sophisticated and the computations more involved. In this paper we refine parts of the algorithm to find Liouvillian solutions of third order equations. We show that, except for four finite groups and a reduction to the second order case, it is possible to give a formula in the imprimitive case. We also give necessary conditions and several simplifications for the computation of the minimal polynomial for the remaining finite set of finite groups (or any known finite group) by extracting ramification information from the character table. Several examples have been constructed, illustrating the possibilities and limitations.     

The computer method of variable piecewise polynomial approximation of functions and solutions of ordinary differential equations

The authors present a computer method of piecewise polynomial approximation of functions and solution of Cauchy problem for systems of ordinary differential equations based on the Newton polynomial. The approximating polynomial on a subinterval is converted to the form with numerical coefficients, the degree of the polynomial and the number of subintervals varies. The method is shown to uniformly converge at the rate of geometric progression under conditions of double continuous differentiability of the function and of the right-hand side of the system. The approximate solution of the system is continuous, continuously differentiable, and is characterized by low error rate, in particular, when solving stiff problems.     

Solving polynomial systems via symbolic-numeric reduction to geometric involutive form

We briefly survey several existing methods for solving polynomial systems with inexact coefficients, then introduce our new symbolic-numeric method which is based on the geometric (Jet) theory of partial differential equations. The method is stable and robust. Numerical experiments illustrate the performance of the new method.     

Discrete-time optimal control for stochastic nonlinear polynomial systems

This paper presents a solution to the discrete-time optimal control problem for stochastic nonlinear polynomial systems over linear observations and a quadratic criterion. The solution is obtained in two steps: the optimal control algorithm is developed for nonlinear polynomial systems by considering complete information when generating a control law. Then, the state estimate equations for discrete-time stochastic nonlinear polynomial system over linear observations are employed. The closed-form solution is finally obtained substituting the state estimates into the obtained control law. The designed optimal control algorithm can be applied to both distributed and lumped systems. To show effectiveness of the proposed controller, an illustrative example is presented for a second degree polynomial system. The obtained results are compared to the optimal control for the linearized system.     

Multidimensional structured matrices and polynomial systems

We apply and extend some well-known and some recent techniques from algebraic residue theory in order to relate to each other two major subjects of algebraic and numerical computing, that is, computations with structured matrices and solving a system of polynomial equations. In the first part of our paper, we extend the Toeplitz and Hankel structures of matrices and some of their known properties to some new classes of structured (quasi-Hankel and quasi-Toeplitz) matrices, naturally associated to systems of multivariate polynomial equations. In the second part of the paper, we prove some relations between these structured matrices, which extend the classical relations of the univariate case. Supported by NSF Grant CCR 9625344 and PSC CUNY Awards Nos. 667340