AF: Small: Symbolic computation with sparsity, error checking and error correction

North Carolina State University, Raleigh NC

Investigators

Abstract

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.