Erich L. Kaltofen - US grants

This project conducts research in the design of efficient algorithms, their implementation in software packages, and in making the programs accessible to non-specialist users of symbolic computation systems. Packages for the black box representation of symbolic objects and for symbolic objects containing imprecise, that is, floating point data will be constructed. The packages are generically programmed as C++ template classes with abstract underlying arithmetics; they can be compiled with a variety of fast libraries for the basic field, floating point, and polynomial operations. A server/client interface seamlessly attaches the packages to all widely-used general purpose symbolic systems such as Maple and Mathetmatica. Parallel execution of the implemented algorithms will be facilitated. Black box objects are stored as functions. For instance: a black box polynomial is a procedure that takes values for the variables as input and evaluates the polynomial at that given point; a black box matrix is a procedure that takes an arbitrary vector as input and computes the matrix times vector product. The FoxBox system is a package for computing greatest common divisors and factoring black box polynomials. The aim is to eliminate algorithmic bottlenecks in FoxBox and add black box linear algebra. For sake of speed, the project focuses on algorithms over finite fields. Efficient server/client bridge code to a variety of general purpose systems will be developed. The project will also investigate how inexact (e.g., floating point) data can be handled in the course of a symbolic computation. The allowance of floating point coefficients in a symbolic, i.e., parameterized model, is crucial for a symbolic approach to problems from the physical world. Moreover, floating point arithmetic is faster than exact arithmetic, especially for algebraic numbers. Several numerical models, such as a-posteriori iterative improvement and sensitivity analysis for perturbed input data, will be considered. The problems of Toeplitz matrix rank, polynomial complex root location, and factoring complex polynomials in many variables will be investigated. The design of a plug-and-play symbolic/numeric package will be studied.

Erich Kaltofen proposes to study mathematical optimization techniques on problem formulations that are imprecise due to numerical data; randomization techniques that are the power tools in the design of fast algorithms with exact arithmetic on black box matrices; and generalization of the computer programs that implement these algorithms to multiple domains with methodologies such as generic, reusable programming and interface protocols.

A difficulty in the symbolic/numeric area is that inputs with imprecise coefficients as a result of a physical measurement or a numerical computation can lack a known property that is of interest. For example, instead of a double real root, a polynomial has two conjugate complex roots that are very close together. The optimization problem is to compute efficiently the nearest input that has the desired singularity.
Our focus will be on the nearest pair of polynomials with a common root under coefficient-wise change (infinity norm), the nearest singular Toeplitz matrix, and the nearest bi-variate complex polynomial that factors over the complex numbers, the latter two under any reasonable norm.

A black box matrix is stored as a function that performs the matrix-times vector product. Efficient algorithms for performing linear algebra computations with exact field arithmetic, such as solving a linear
system with a black box coefficient matrix, are based on the Lanczos/Wiedemann approach.
Randomization techniques, for instance, matrix pre-conditioning and Krylov sub-spacing with random projections, avoid self-orthogonality when the coefficients are from a finite field and general algorithmic
break-down due to certain invariant factors of the matrix. We propose to investigate how the different linear algebra problems are interelated, for example if the computation of a solution of an inhomogeneous black box linear system can be efficiently reduced to the computation of a column dependency of a black box matrix.

Generic programming is a software design technique that generalizes a program so that it can be used with more than one underlying domain. The proposed implementation of our black box algorithms not
only permits the plug-in of a black box matrix over a native coefficient field, but the code also imports internally needed operations like polynomial and vector operations from expertly fine-tuned existing packages across generic interfaces. Our library's application program interface provides a serialization mechanism for black box objects that is compliant with the MathML/OpenMath philosophy and that allows
Internet communication.

Finally, we propose research on two classical problems. First, the polynomial-time computation of dense, low-degree factors of high-degree sparse multi-variate polynomials with rational coefficients, which would generalize a recent related result by Hendrik W. Lenstra, Jr. Second, a time- and space-efficient realization of the transposition principle for transforming a matrix-times-vector function to the transpose vector-times-matrix operation.

The LinBox group of twelve researchers in three countries (USA, France, Canada) proposes research in the design of efficient algorithms for linear algebra, in their implementation in a software library, and in how to interface the library to widely-used scientific computing software. Algorithms will be implemented, and new algorithms designed, for the black box representation of matrices---hence the name LinBox---over entry domains that are either symbolic, that is, exact, or floating point, that is, inexact. The library is generically programmed as C++ template classes with abstract underlying arithmetics; they can be compiled with a variety of fast libraries for the basic field, floating point, and polynomial operations. A server/client interface seamlessly attaches the library to the common general purpose symbolic systems Maple and Mathematica and to the numeric system MatLab. Parallel execution of the implemented algorithms is facilitated.

Black box matrices are stored as functions (as linear operators in effect): the matrix is a procedure that takes an arbitrary vector as input and efficiently computes the matrix-times-vector product. Black box linear algebra generalizes sparsity. The LinBox library will contain algorithms for solving singular and non-singular systems of linear equations whose coefficient matrix is given in black box representation. Furthermore, it is proposed to develop fast methods for the rank and the minimal and characteristic polynomial of a black box matrix. Finally, LinBox will contain methods for linear Diophantine problems with black box matrices, such as computing an integral solution to a linear system with integer entries and computing the Smith normal form of an integer matrix.

Erich Kaltofen is studying the connection of the bit cost of arithmetic on the numeric coefficients to the overall efficiency of symbolic computation algorithms. He designs and implements new algorithms for fundamental problems in exact polynomial and linear algebra and such polynomial resultants that achieve speedup through controlling the lengths of the intermediately computed rational numbers. Faster arithmetic cost is also achieved by fixed or variable precision floating point operations, and such approximate input and output data is the subject of our investigations into hybrid symbolic/numeric algorithms for polynomial factorization and structured system solving. Randomized algorithms for sparse interpolation problems are being executed as good heuristics with a limited number of coin flips in order to keep intermediate coefficients small. The algorithms in the LinBox program library for sparse, structured and black box matrices through its generic, reusable design are compiled with arithmetic that is specialized, for example, for particularly efficient finite field operations.

The overarching goal of the field of symbolic computation is doing mathematics with the aid of a computer. Programs such as Mathematica by Wolfram Research Inc. and Maple by Maplesoft have already reached millions of users, who use them to automatically and error-free perform the mechanics of mathematical manipulation. Thus, the users can concentrate on the interpretation of the mathematical results and, equally important, manipulate large mathematical models that are closer to reality. Kaltofen's research contributes to the infrastructure of the underlying mathematics engine on the computer. The investigated speedups make the execution significantly faster, thus allowing even better models and providing mathematics servers to even more users ranging from practicing scientists to high school students. Kaltofen under the umbrella of the LinBox group (www.linalg.org) is making the developed software freely available. Users can download and run the algorithms and experts in the discipline can scrutinize the fine points.

This the first International Conference Applied Computer Algebra (ACA), held in Raleigh North Carolina, July 28-31, 2003. In the past several years there has been a dramatic increase in the applications of computer algebra (CA) in engineering, science and education. The goal of this conference is to facilitate this important progress through an international meeting that emphasizes applications of computer algebra and interdisciplinary interaction between computer algebra researchers and serious users from other disciplines. The ACA conference complements nicely the already well-established conferences, such as ISSAC, which are essentially the intradisciplinary forum for computer algebra researchers on fundamental theories (rather than applications and inter-disciplinary interaction). The conference is organized as a collection of twelve mini workshops (sessions) organized by prominent researchers and focused on their own application areas including education, engineering, physical sciences, economics and life/medical sciences.

This conference will have the broad impact on two communities: the huge user community and the research community. The user community will be able to learn about the state of the art theories and algorithms that are proven to be applicable. The research community will be able to learn about important problems/challenges facing the serious users from other disciplines, inspiring fresh new theoretical research and algorithm design.

Erich Kaltofen is studying efficient algorithms for symbolic computation problems in linear and polynomial algebra that can impact applications such as geometric modeling, diophantine optimization, or cryptography. The overarching goal of the field of symbolic computation is performing mathematical computations by computer. Programs, such as Mathematica by Wolfram Research Inc. and Maple by Maplesoft, have already reached millions of users, who use them to automatically and without error perform the mechanics of mathematical manipulation. Our research affects broadly the functionality and efficiency of the underlying mathematics engine on the computer. The investigated problems provide algorithms for new tasks, and make the execution of existing procedures significantly faster, thus allowing computation with bigger models and providing mathematics servers to more users ranging from practicing scientists to high school students. Several of the algorithms have immediate application to engineering problems such as the design of Stewart-Gouch platforms. Kaltofen, under the umbrella of the LinBox group (www.linalg.org), is making the developed software freely available.

The problem of decomposing a curve, surface or zero-set of polynomial equations into their components hinges on multivariate polynomial factorization. When the coefficients are imprecise due to floating point truncation or empirical measurement, the factorizations cannot be exact but must approximate the input data. We study sparse multidimensional models through employing the significant recent progress in hybrid symbolic/numeric algorithms for sparse interpolation and dense bi- and trivariate approximate polynomial factorization. Our research in exact sparse and structured linear algebra algorithms studies the control of the lengths of the intermediately computed rational numbers and the use of residue arithmetic modulo a power of 2. In the subject of polynomial factorization, we seek polynomial-time algorithms and NP-hardness proofs for problems on what we call supersparse polynomials, i.e., polynomials where the term degrees can have hundreds of digits as binary numbers. We also investigate efficient solutions for standard factorization problems, such as factorization by substituting a term for the variable. Finally, we study the problem of computing the determinant without a division and of deriving pure determinantal formulas for the resultant.

The Department of Mathematics at NC State University proposes to create a high performance computational cluster to support the research of the symbolic computation group. The Department is one of the largest groups in symbolic computation in the USA. The group is composed of 6 faculty (4 professors and 2 assistant professors), 11 PhD. students and 1 Masters student. The field of Symbolic Computation has, by its very nature, been pushed forward by the symbiotic relationship between the development of computational tools and the development and implementation of good algorithms. This relationship is reflected in the various research projects supported by this award. The research relies heavily on the ability to compute examples and test proposed algorithms, not only to see what is true but also to see which algorithms truly work.

Symbolic Computation is of fundamental importance throughout science and industry. It forms the basic building blocks of the mathematical programs, like Matlab, Mathematica, Maple and many others, all of which have become fundamental tools throughout science. The work of the symbolic computation group at NC State University will help expand these programs to become even more powerful and at the same time improve their usability. This will enable more and more people to take advantage of these powerful mathematical tools. Good symbolic computation packages will turn theoretical models into practical software. These packages will provide an easier approach to a highly technical area for students at many levels of mathematics, and researchers from many branches of science and engineering.

The discipline of symbolic computation provides advanced software for cyber-enabled discovery and innovation. Symbolic methodologies and programs are applied to problem solving and model discovery in

--scientific computing,
--physics,
--mathematics,
--inter-system communication protocols and standards,
--categorical language design, generic programming and compilation,

and more. Due to the complexity of the arising computations, parallel and distributes environments are coming into use, symbolic and numeric approaches are combined into hybrid methods, and semantic verification and output certification (e.g., through Las Vegas randomization and numerical error analysis) are performed.

We propose to gather in late October or early November 2007 in Washington DC a group of 24--30 invited internationally recognized experts from academia and industry in both symbolic computation and its CDI applications disciplines (e.g., numerical computing, physics, mathematics, computing language design and compilation, parallel and distributed computation, program interface design) for a one and one half day workshop. The objectives of our workshop are to discuss and produce a report on possible research directions and their synergies for CDI through symbolic computation, both in the symbolic computation and the applications disciplines. Novel uses of symbolic computation can be sparse model construction by hybrid symbolic/numeric methods, sparse exact matrix computations for problems from physics and mathematics, multi-level parallel software design for polynomial system solution and non-linear optimization, high-level categorical and verifiable program design, algorithm synthesis, and more.

ABSTRACT:

A mathematical model for a natural (e.g., the heart beat of a
human) or man-made process (e.g., the radio wave of a wireless
signal) is a mathematical expression or an algorithm that on
evaluation of system parameters (such as a point in time) yields
a model value (e.g., the amplitude of a wave). Models are
created by understanding the process, which suggests the form
of the expression, and by observing and measuring an actual
process. From those data points the best model is fitted by
a computation. Erich Kaltofen studies both how to fit to data
certain models, such as fractions of sparse polynomials, and
then how to certify that the computation has produced the best
possible model. The algorithms for creation of best fits and
subsequent certification of optimality can be compute-intensive
and require multi-processor computing environments.

Erich Kaltofen and his students and collaborators will design
algorithms for symbolic models such as sparse multivariate
rational functions and formulas with very large and even
parametric exponents. Our algorithms can work with both exact
and approximate data, the latter by hybrid symbolic/numeric
techniques. Computation with floating point scalars requires
a new kind of probabilistic analysis when randomization is
applied, and we will make use of recent results on estimating
the spectra and condition numbers of random matrices. One
application of such randomization is the efficient solution
of highly under- and overdetermined dense linear systems.
A new alternative to error analysis is the exact validation via
symbolic computation of the global optimality of our approximate
solutions. Semidefinite programming and Newton refinement
are used to compute a numerical sum-of-squares representation,
which is converted to an exact rational identity for a nearby
rational lower bound. Since the exact certificates leave no
doubt, the numeric heuristics need not be fully analyzed.
We will search for rationalizations that can validate very
large sums-of-squares and hence apply to large inputs. We will
develop parallel and distribute computing tools for the arising
symbolic and hybrid symbolic-numeric computation tasks.

The solution of symbolic computation problems can be accelerated in at least two ways: one is to integrate limited precision floating point arithmetic on the scalars, and the other is to use parallel processes. We propose to investigate those approaches on problems in real algebraic optimization and exact linear algebra.

Semidefinite numerical optimization produces sum-of-squares representations for polynomial inequalities, which express global optimality. But the representations are numeric and approximate, and exact rational certificates for the inequalities are derived via exact symbolic means, thus leading to truly hybrid symbolic-numeric algorithms. When combining floating point arithmetic and randomization, analysis of the expected condition numbers of the random intermediate problems can guarantee success. We propose to introduce fraction-free algorithms and analyze the arising determinantal condition numbers.

LinBox is a C++ library for exact linear algebra. We propose to participate in the parallelization of the LinBox library by investigating problems with memory contention and by creating interactive symbolic supercomputing environments. Several related problems in computational algebraic complexity that will receive attention are: quadratic-time certificates for linear algebra problems, determinantal representation of polynomials by symmetric linear matrix forms, and interpolation of supersparse (lacunary) rational functions.

The PI's research expands the infrastructure in symbolic computation and the understanding of the underlying complexity. Aside from certifying optima, exact sums-of-squares certificates have proved theorems in mathematics, physics and control theory. Some of the important applications of LinBox are sparse linear algebra over finite fields and integer Smith forms for computational topology data. The PI is making the developed software freely available.

Algorithmic thinking and computation have become a cornerstone of modern science (pure and applied) and modern life. Symbolic computation programs, such as Mathematica, Maple, and the SAGE platform, have many applications, such as modeling data sets by symbolic expression for Toyota and Shell Oil, generating programs for signal processing, and program and protocol verification.

A hallmark of symbolic computation is that the outputs are exact. Digital error correcting decoding produces exact outputs from inputs in which some entries are incorrect, and minimizes the required redundancy. Symbolic polynomial interpolation algorithms take advantage of sparsity. Kaltofen proposes to create algorithms that can interpolate sparse uni- and multivariate polynomials and rational functions from evaluations where some of the values are incorrect. A goal is to minimize the amount of oversampling that is necessary to locate and correct those faulty evaluations. Hybrid symbolic-numeric computation accepts approximate scalar entries in the inputs, which can be imprecise because they come from a floating point computation or a physical measurement. Sparse multivariate polynomial interpolation has been adapted to such data, for purpose of constructing sparse models for the observed measurements, and Kaltofen proposes to create hybrid symbolic-numeric versions of our interpolation algorithms that can correct outlier errors. In addition, Kaltofen proposes to construct easily verifiable certificates for complex non-linear problems, such as certificates that a real multivariate polynomial is unbounded or that a symmetric real matrix is positive definite. Both problems are important for global non-linear optimization. Lastly, Kaltofen proposes to apply the matrix generalization of the Berlekamp/Massey algorithm and the multidimensional generalization by Shojiro Sakata to recurrences with polynomial coefficients, such as the sequence of the factorials and the binomial coefficients. He will also study how to correct errors in the linear generated arrays.

Kaltofen's proposed research combines hybrid symbolic-numeric computation with digital error-correcting decoding for purpose of removing outliers in sparse model synthesis, which constitutes a brand-new approach for ``cleaning-up'' errors in data sets. Certificates that prove that computed minima are global minima permit the use of unproven algorithmic heuristics in the optimization methods, especially algorithms with floating point arithmetic whose stability is not analyzed, and greatly broaden what can be placed in publishable software: the programs do not give a false output. Lastly, recurrences are fundamental tools in symbolic computation algorithms. Kaltofen is making the developed software for the algorithms freely available.

This project continues the PI's productive work in certifying the results of symbolic computations and in polynomial computations. It aims for results in three areas:
1. Low-cost certification of the output of large-scale symbolic computations performed on high power servers, possibly in the computing cloud. The focus is on problems in high-dimensional linear algebra and non-linear optimization. Quickly checkable proofs can also expose bugs/faults in time- and space-consuming server computations.
2. Medical image processing needs robust interpolation from values sampled at points; The project will reconstruct functions as sparse sums of a few exponentials or orthogonal polynomials, using algorithms that account for noise and outliers (that is, catastrophic errors) while minimizing the number of sample points.
3. In fundamental problems in algebraic computational complexity, it takes a fresh look at polynomial multiplication and greatest common divisors.

The PI continues to train undergraduate and Master students, and supervise Ph.D. students and a postdoctoral scholar, so that they develop advanced skills in designing algorithms and computer programs for doing mathematics. The students and postdoc will be encouraged to adopt advanced research communication skills by presenting posters and talks at international meetings, especially when their background is from under-represented groups in the discipline.

The method to achieve the goal of low-cost certification is to develop certificates for the Frobenius form of sparse matrices and for the solvability of polynomial equations over the real numbers that are independent of the algorithms that produce the output. The approach is based on interactive proof protocols and crytographic hardness assumptions, but the project aims to reduce the use of cryptography in its protocols, so that the verifier can increase probability of correctness arbitrarily, even after the computation. The PI has used algebraic error correcting decoding to locate evaluation errors in sparse interpolation and dense rational vector recovery, the latter with early termination. The current focus is on sparseness in a Chebyshev basis, where list-decoders are missing, and on multivariate sparse interpolation using a generalization of Prony's Algorithm combined with Sakata's generalization of the Berlekamp/Massey Algorithm. Finally, the project studies the algebraic complexity of multiplying polynomials without the use of constants, computing the Sylvester resultant without divisions, and representing polynomials as the characteristic polynomial of matrices.