Foundations of Computational Mathematics

We consider a semi-algebraic set S defined by s polynomials of degree at most d in k variables contained in an algebraic variety V of dimension k’ defined as the zero set of a polynomial of degree d and two points defined by polynomials of degree t. We present an algorithm for computing a semi-algebraic path in S connecting two points if they happen to lie in the same connected component of S which works in time $$({s^{k' + 1}} + k's{t^{0(1)}}){d^{O({k^2})}}$$.

We introduce a new class of real-valued locally Lipschitz functions, which we call arc-wise essentially smooth, and we show that if g : Rn → R is arc-wise essentially smooth on Rn and each function f_j : Rm → R, 1 ≤ j ≤ n is strictly differentiable almost everywhere in Rm, then g ◯ f is strictly differentiable almost everywhere in Rm, where f ≡ (f₁, f₂, …f_n). We also show that all the semi-smooth and pseudo-regular functions are arc-wise essentially smooth. Thus, we provide a large and robust lattice algebra of Lipschitz functions whose generalized derivatives are extremely well-behaved.

Models for image smoothing have not fully incorporated the restrictions imposed by the physics of image generation. In particular, any image smoothing process should respect the essential singularities of images (which we call junctions) and should be invariant with respect to contrast changes. We conclude that local image smoothing is possible provided singular points of the image have been previously detected and preserved. We define the associated degenerate partial differential equation and sketch the proof of its mathematical validity. Our analysis uses the phenomenological theory of image perception of Gaetano Kanizsa, whose mathematical translation yields an algorithm for the detection of the discontinuity points of digital images.

Various proposals have recently been made which cast cortical processing in terms of hierarchical statistical generative models (Mumford, 1994; Kawato, 1993; Hinton & Zemel, 1994; Zemel, 1994; Hinton et al, 1995; Dayan et al, 1995; Olshausen & Field, 1996; Rao & Ballard, 1995). In the case of vision, these claim that top-down connections in the cortical hierarchy capture essential aspects of how the activities of neurons in primary sensory areas are generated by the contents of visually observed scenes. The counterpart to a generative model is its statistical inverse, called a recognition model (Hinton & Zemel, 1994). This takes low-level activities and produces probability distributions over the entities in the world that could have led to them, expressed as activities of neurons in higher visual areas that model the image generation process. Even if a generative model is computationally tractable, its associated recognition model may not be. In this paper, we study various different types of exact, sampling-based and approximate recognition models in the light of computational and cortical constraints.

We generalize the notion of ordered and metric ∑—algebras to algebras where the carriers are continuity spaces [9]. The main motivation for this generalization comes from the subject of Real Number Computation. We aim at providing the scientific computing programmer with tools from the formal specification theory in order to achieve a rigorous development and analysis of numerical programs.Classification of topics covered: abstract data types, program specification, exact real arithmetic, lazy functional languages, continuity spaces.

Is a sparse polynomial system more easy to solve than a non sparse one? In this paper we introduce a new invariant, the sparse condition number, and we study sparse polynomial system analysis in terms of this invariant.

Let f₁,…, f _n be Laurent polynomials in n variables with a finite set V of common zeroes in the torus T = (ℂ✶)n. The total residue of the differential form $${\Phi _q} = \frac{q}{{{f_1} \cdots {f_2}}}\frac{{d{t_1}}}{{{t_1}}} \wedge \cdots \wedge \frac{{d{t_n}}}{{{t_n}}},$$, i.e. the sum of the local Grothendieck residues of a Laurent polynomial q, at each of the points in V, with respect to f₁,…,f _n , is a rational function of the coefficients of the f’s which has interesting applications in a number of different contexts such as: integral representations formulae in complex analysis; explicit division and interpolation formulae and effective bounds for problems in commutative algebra (see [3] which contains an extensive bibliography); duality methods in the study of algebraic questions such as the ideal membership problem, computation of traces, elimination, complexity bounds, etc. ([2, 6, 8, 9, 10, 15]).

The purpose of this note is to report on some recent results concerning QR factorizations of smooth full rank matrices. The focus of this note is on the computation of the Q factor. In particular, unlike previous works on the subject, we report on two techniques based on reflectors and rotators which achieve piecewise smooth factorizations (see [7]). The benefits of the present techniques is that they can be implemented rather inexpensively, and that maintaining orthonormality for the Q factor is easy to guarantee even for rectangular matrices.

The aim of this paper is to present algorithms to compute finite semigroups. The semigroup is given by a set of generators taken in a larger semigroup, called the “universe”. This universe can be for instance the semigroup of all functions, partial functions, or relations on the set <1,…,n>, or the semigroup of × n matrices with entries in a given finite semiring.The alogrithm produces simultaneously a presentation of the semigroup by generators and relations, a confluent rewriting system for this presentation and the Cayley graph of the semigroup. The elements of the semigroups are identified with the reduced words of the rewriting systems.We also give some efficient algorithms to compute the Green relations, the local subsemigroups and the syntactic quasi-order of subsets of the semigroup.

In this paper, we give an extension of the Grzegorczyk Hierarchy to the BSS theory of computability which is a generalization of the classical theory. We adapt some classical results ([3, 4]) related to the Grzegorczyk hierarchy in the new setting.

Affine invariant symmetry sets of planar curves are introduced and studied in this paper. Two different approaches are investigated. The first one is based on affine invariant distances, and defines the symmetry set as the closure of the locus of points on (at least) two affine normals and affine-equidistant from the corresponding points on the curve. The second approach is based on affine bitangent conies. In this case the symmetry set is defined as the closure of the locus of centers of conies with (at least) three-point contact with two or more distinct points on the curve. Although the two analogous definitions for the classical Euclidean symmetry set are equivalent, this is not the case for the affine group. We present a number of properties of both affine symmetry sets, showing their similarities with and differences from the Euclidean case.

An arbitrary consistent one-step approximation of an ordinary differential equation is studied. If the scheme is assumed to be accurate of O(△tr) then it may be shown to be O(△tr+m) accurate as an approximation to a modified equation for any integer m ≥ 1. A technique is introduced for proving that the modified equations inherit qualitative properties from the numerical method. For Hamiltonian problems the modified equation is shown to be Hamiltonian if the numerical method is symplectic, and for general problems the modified equation is shown to possess integrals shared between the numerical method and the underlying system. The technique for proving these results does not use the well-known theory for power series expansions of particular methods such as Runge-Kutta schemes, but instead uses a simple contradiction argument based on the approximation properties of the numerical method. Although the results presented are known, the method and generality of the proofs are new and may be of independent interest.

It is often known from theoretical analysis that the exact solution of an ordinary differential system lies on a specific differentiable manifold and there are important advantages in retaining this feature under discretization. In this paper we examine whether the correct manifold is retained by a class of discretization methods that includes explicit multistep and multiderivative schemes. We obtain a necessary and sufficient condition for the retention of invariance under discretization. In particular, we prove that no such method can be expected to stay on a quadratic manifold. More specifically, given such a method and an arbitrary quadratic manifold N, there exists an ordinary differential equation whose exact solution lies on N, yet its discretization by the underlying method departs from the manifold.

In the present paper we propose a new technique for the numerical solution of the Schrödinger equation with the commonly arising nonlinearity 1$$i{\psi _t} + {\psi _{xx}} + f\left( {{{\left| \psi \right|}^2}} \right)\psi = 0,$$, where in the term of f we take the polynomial of the l-th degree: 2$$f \equiv f\left( {{{\left| \psi \right|}^2}} \right) = \sum\limits_{t = 0}^N {{\alpha _l}} {\left| \psi \right|^{2l}} = {\alpha _0} + {\alpha _1}{\left| \psi \right|^4} + \cdots + {\alpha _N}{\left| \psi \right|^{2N}}.$$. Depending on the number of terms in the series and also on the coefficients of (2) (we suppose that α₀, α₁, • • • are arbitrary in general), eq.(l) arises in various branches of physics.

Let P ∈ C[z] be a polynomial which has a cluster of k zeros near v₀ ∈ C. The coefficients of the factor F of P corresponding to this root cluster can be computed from the coefficients of P by Newton iteration in Ck, applied to the mapping F ↦ P mod F.This paper presents and analyzes a numerical algorithm based on this idea. The algorithm uses only polynomial multiplication and division. In particular, there is no need to solve linear systems.The analysis results in an explicit quantitative condition for the coeficcients of P which guarantees the algorithm to converge when started with P₀ = (z — v₀)k. Efficient test procedures for this condition are described. Finally, another starting value condition in terms of root sizes is proved and illustrated with some examples.

A remarkable lemma of Szemerédi asserts that, very roughly speaking, any dense graph can be decomposed into a bounded number of pseudorandom bipartite graphs. This far-reaching result has proved to play a central role in many areas of combinatorics, both ‘pure’ and ‘algorithmic.’ The quest for an equally powerful variant of this lemma for sparse graphs has not yet been successful, but some progress has been achieved recently. The aim of this note is to report on the successes so far.

The attractor of a 3-manifold M3 is the set of all 3-gems which have a minimum number of vertices and induce M3. A gem (graph-encoded manifold) is a special edge graph which encodes a ball complex whose underlying space is a manifold. Every 3-manifold is induced by a 3-gem. In this article I briefly recall the definitions and terminology of 3-gems, state some of the properties of attractors and list a number basic open questions concerning them. The characteristic of this approach to 3-manifolds is the massive use of computers and so, most of the open questions here stated simply await proper implementation of algorithms to be answered.

We introduce a new model algorithm for solving nonlinear programming problems. At each iteration, the method solves (approximately) linearly constrained optimization problems. For this reason, it belongs to the class of SLCP (Sequential Linearly Constrained Programming) methods. Each iteration begins with a Restoration Phase, where feasibility of the current iterate is improved and follows with a Minimization Phase of Trust-Region type. In the Minimization Phase the objective function is reduced within an approximate (linearized) feasible set. The current point and the trial point obtained in the Minimization Phase are compared on the basis of a nonsmooth merit function that combines feasibility and optimality. We prove global convergence results.

We define a new complexity measure: the height of an additive machine. This quantity is the amount of space necessary to code in binary any number computed by the machine as a linear integral combination of its input and constants. We give some arguments in favor of the following thesis: height in additive machines is equivalent to space in Turing machines. Among our results we emphasize: The existence of a height hierarchy.The class of sets decidable in polynomial height equals the class of sets decidable in parallel polynomial time.A version of Savitch’s theorem for the height.The existence of a hierarchy for nondeterministic height.

We use a theorem by Borodin relating parallel time with sequential space in order to obtain algorithms that require small space resources. We first apply this idea to some linear algebra problems. Then we reduce several problems of Elimination Theory to linear algebra computations and establish PSPACE bounds for all of them. Finally, we show how this strategy can be improved by means of probabilistic arguments.

In a series of papers Saul Gelfand and myself ([1], [2]) have developed a theory of discrete-time stochastic recursive algorithms for obtaining the global minima of functions. These algorithms are generalizations of stochastic approximation algorithms which usually exhibit only local convergence. The key idea in our work is the elucidation of the role of a stochastic differential equation in the analysis of the recursive algorithm. This stochastic differential equation plays the same role as the ordinary differential equation plays in the analysis of ordinary stochastic approximation algorithms. In this talk ([4], [5]) I present a wide ranging generalization of these ideas to recursive algorithms which arise in adaptive parameter estimation, various signal processing algorithms, maximum likelihood estimation and quantization. These algorithms are global versions of algorithms presented in Beneveniste, Metivier and Priouret [3]. This work sheds new light on the behavior of ordinary stochastic approximation algorithms.

We consider a model of analog computation which performs language recognition in real time. We encode an input word as a point in ℝd by composing iterated maps, and then apply inequalities to the resulting point to test for membership in the language.

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 apply some results on computations with matrices of these new classes, together with some techniques from algebraic residues theory, in order to devise an algorithm for approximating a selected solution of a polynomial system of the form $$ \left\{ {\begin{array}{*{20}{c}} {x_{1}^{{{{d}_{1}}}} - {{R}_{1}}({{x}_{1}},...,{{x}_{n}}) = 0} \\ \vdots \\ {x_{n}^{{{{d}_{n}}}} - {{R}_{n}}({{x}_{1}},...,{{x}_{n}}) = 0} \\ \end{array} } \right. $$ where deg (R _i < d _i . The complexity of this algorithm is O(D2 log(D)c), where D = П _i=1n d _i is the number of roots of the system.

We present an overview of intrinsic integration schemes for differential equations evolving on manifolds, paying particular attention to homogeneous spaces. Various examples of applications are introduced, showing the generality of the methods. Finally we discuss abstract Runge-Kutta methods. We argue that homogeneous spaces are the natural structures for the study and the analysis of these methods.

The generalized Davidson algorithm can be seen as a method which uses preconditioned residuals to create a subspace where it is easier to find the smallest eigenvalue and its eigenvector. In this paper theoretical results proving convergence rates are shown. In addition, we investigate the use of multigrid as a preconditioner for this method and describe a new algorithm for calculating some other eigenvalue-eigenvector pairs as well, while avoiding problems of misconvergence. The advantages of implicit restarts are also investigated.

A variational formulation for the image segmentation problem due to D. Mumford and J. Shah has risen a number of mathematical problems, which are interesting both from the point of view of applications and in their own right. In this paper we report on some results concerning the existence and the regularity of the solutions of a class of variational problems whose prototype is the Mumford-Shah problem.

In this paper we focus on tests and constructions of irreducible polynomials over finite fields. We revisit Rabin’s (1980) algorithm providing a variant of it that improves Rabin’s cost estimate by a log n factor. We give a precise analysis of the probability that a random polynomial of degree n contains no irreducible factors of degree less than O(log n). This probability is naturally related to Ben-Or’s (1981) algorithm for testing irreducibility of polynomials over finite fields. We also compute the probability of a polynomial being irreducible when it has no irreducible factors of low degree. This probability is useful in the analysis of various algorithms for factoring polynomials over finite fields. We present an experimental comparison of these irreducibility methods when testing random polynomials.

This work involves two-stage approaches to enhancing the quality of images taken through the atmosphere. First, a matrix control problem arising in adaptive-optics is discussed. The problem involves optimal real-time control of very fast-acting deformable mirrors designed to compensate for atmospheric turbulence and other image degradation factors, such as wind-induced telescope vibration (windshake). The surface shapes of the mirrors must change rapidly to correct for time-varying optical distortions. The second stage of compensating for the effects of atmospheric turbulence generally occurs off-line, and consists of the post-processing step of image restoration. Here, the work involves large-scale computations, using either a simultaneous image of a natural guide star or a large ensemble of images corresponding to different atmospheric realizations, to deconvolve the blurring effects of atmospheric turbulence.

In this paper, we derive an explicit and symplectic integration scheme for elastic rods. To do so, we first discuss various spatial discretizations that yield an appropriate finite-dimensional truncation of the Simo-Marsden-Krishnaprasad formulation of rod dynamics [1]. Then, similar to rigid body dynamics [2], we formulate an explicit time-integrator by splitting the Hamiltonian in an appropriate way. The resulting scheme is 2nd order, explicit, symplectic, and preserves the underlying symmetries of rod dynamics. We also consider the case of an unshearable and unextensible rod. It is demonstrated that this leads to a Hamiltonian formulation with holonomic constraints that can be integrated by an appropriate modification of the constrained schemes considered in [3]. Application of our scheme also includes continuum models of DNA [4].

This paper reexamines univariate reduction from a toric geometric point of view. We begin by constructing a binomial variant of the u-resultant and then retailor the generalized characteristic polynomial to sparse polynomial systems. We thus obtain a fast new algorithm for univariate reduction and a better understanding of the underlying projections. As a corollary, we show that a refinement of Hilbert’s Tenth Problem is decidable in single-exponential time. We also obtain interesting new algebraic identities for the sparse resultant and certain multisymmetric functions.

Using inertial manifold theory, a finite-dimensional feedback controller is constructed for a nonlinear parabolic partial differential equation so that the dynamics of the closed-loop system is close in a weighted C1-metric for the vector fields to a finite dimensional dynamics prescribed in advance. As a consequence, some structurally stable dynamics, for instance, can be imposed on the controlled system.

The underlying theme of this talk is the jacobian matrix of a (finite) set of multivariate polynomials f = {ℓ₁…-, ℓ_m} ⊂ R = k[X] = k[X₁…,X_d]. Here k stands for a field, eventually of characteristic zero. Jacobian matrices are classical, useful in almost all branches of mathematics and there is a famous conjecture that bears the name! Is this enough reason to make them a central theme in a talk? Perhaps. The full justification here would go far beyond our modest purpose which is, namely, to convey their theoretical and computational usefulness in everyday commutative algebra and algebraic geometry.

Rigid body dynamics with unilateral constraints, collisions and Coulomb friction has been the subject of investigation and controversy for the past century, due to the failure to obtain solutions in certain situations. Recent extensions to the theory of ordinary differential equations, notably J.J Moreau’s measure differential equations can be used to give a clearer idea of the issues in these problems. Novel numerical methods have had to be developed to solve these problems, and to prove the convergence of the numerical trajectories to solutions of the true rigid body problem.

We consider the computational power of neural networks constructed by partitioning algorithms. These neural networks can also be viewed as decision lists with tests evaluating linear functions. An exponential lower bound is proved for the complexity of an explicit Boolean function in this model. The lower bound is extended to decision trees of bounded rank. We also discuss the relationship between these models and the hierarchy of threshold circuit complexity classes.

In this paper we analyze the effect of ill-posedness measures on the computational complexity of an interior point algorithm for solving a linear or a quadratic programming problem when finite precision arithmetic is used. The complexity is analyzed from the point of view of the number of iterations required to achieve an approximately optimal solution, as well as from the point of view of the numerical precision required in the computations. This work gives a view of computational complexity based on more “natural” properties of the problem instance.

In the context of devising geometrical integrators that retain qualitative features of the underlying solution, we present a family of numerical methods (the method of iterated commutators, [5, 13]) to integrate ordinary differential equations that evolve on matrix Lie groups. The schemes apply to the problem of finding a numerical approximation to the solution of $$[Y' = A(t,Y)Y,Y(0) = {Y_0}$$ whereby the exact solution Y evolves in a matrix Lie group G and A is a matrix function on the associated Lie algebra g. We show that the method of iterated commutators, in a linear setting, is intrinsically related to Lie’s reduction method for finding the fundamental solution of the Lie-group equation Y’ = A(t)Y.