CAREER: Solving Over-Constrained Systems of Non-Linear Equations by Symbolic-Numeric Methods

North Carolina State University, Raleigh NC

Investigators

Abstract

ABSTRACT PROPOSAL: 0347506 INSTITUTION: North Carolina State U PRINCIPAL INVESTIGATOR: Szanto, Agnes TITLE: CAREER: Solving Over-Constrained Systems of Non-Linear Equations by Symbolic-Numeric Methods Non-linear, over-constrained systems of equations often arise in science and engineering where mathematical models are used for analysis. Such areas include: geo-physical phenomenon, computer graphics and vision, analysis of fluid and mechanical structures. Over-constrained equations are difficult to use, as there are no reliable and efficient methods for solving them. Traditional numerical and symbolic solution methods are not designed to handle either over-constrained systems or inexact coefficients. Thus, this research is exploring the theory, algorithms and software for solving systems of non-linear, over-constrained systems of equations. The goal is to lay the theoretical framework to extend both symbolic and numeric techniques to over-constrained equation systems. Special attention is paid to the integration of the research with graduate education through the development of course plans that give the required foundations for the students to participate in the proposed research. A wide range of application areas is being emphasized. This research considers two types of systems: (1) Over-constrained systems of algebraic equations with inexact coefficients; and (2) Over-constrained systems of differential equations with symmetric solutions. The plan for investigation is: Over-constrained systems of algebraic equations with inexact coefficients. First, a theoretical framework will be laid for reliable computation via meaningful and verifiable notions of solutions together with backward error and conditioning analysis. Next, effort will be made to substantially improve the complexity of existing symbolic-numeric methods by exploiting the possible small cardinality of the solution set. The goal is to devise an algorithm that is polynomial in the input plus the output size. Over-constrained systems of differential equations with symmetric solutions: Recent results on moving frame methods allow to write a differential system in terms of the invariants of a symmetry group, and to design invariant numerical approximations via invariant finite difference equations. In order to apply these techniques on over-constrained differential systems, the investigator will extend algebraic elimination techniques to invariantized non-linear differential systems. However, the application of the invariant differential operators introduces non-commutativity in the associated differential algebra. The goal is to prove termination and give degree bounds for the elimination algorithms. These two problems are actually closely related and thus the investigator will also explore their deep interconnection with the goal of laying the mathematical bases of a unified approach.