On the Complexity of Computing Error Bounds

We consider the cost of estimating an error bound for the computed solution of a system of linear equations, i.e., estimating the norm of a matrix inverse. Under some technical assumptions we show that computing even a coarse error bound for the solution of a triangular system of equations costs at least as much as testing whether the product of two matrices is zero. The complexity of the latter problem is in turn conjectured to be the same as matrix multiplication, matrix inversion, etc. Since most error bounds in practical use have much lower complexity, this means they should sometimes exhibit large errors. In particular, it is shown that condition estimators that: (1) perform at least one operation on each matrix entry; and (2) are asymptotically faster than any zero tester, must sometimes over or underestimate the inverse norm by a factor of at least , where n is the dimension of the input matrix, k is the bitsize, and where either or grows faster than any polynomial in n . Our results hold for the RAM model with bit complexity, as well as computations over rational and algebraic numbers, but not real or complex numbers. Our results also extend to estimating error bounds or condition numbers for other linear algebra problems such as computing eigenvectors. September 10, 1999. Final version received: August 23, 2000.     

On the parallel evaluation of a sparse polynomial at a point

A new version of the Ruffini–Horner rule is presented for the evaluation of a polynomial of degree n at a point. In the PRAM model of parallel computation the new algorithm requires log n parallel steps with n/2+1 processors and the total number of arithmetic operations is n+⌈log₂(n+1)⌉ -1 multiplications and n additions. If the polynomial is sparse, i.e., the number of nonzero coefficients is k≪ n, then the total number of operations is at most k(⌈log n⌉- ⌊log k⌋)+2k+⌈log n⌉. Moreover, similarly to the customary Ruffini–Horner rule, the algorithm is backward numerically stable. In other words, the value provided by applying the algorithm in floating point arithmetic with machine precision μ coincides with the value taken on at the same point by a slightly perturbed polynomial. This revised version was published online in June 2006 with corrections to the Cover Date.     

The random product homotopy and deficient polynomial systems

Summary Most systems ofn polynomial equations inn unknowns arising in applications aredeficient, in the sense that they have fewer solutions than that predicted by the total degree of the system. We introduce the random product homotopy, an efficient homotopy continuation method for numerically determining all isolated solutions of deficient systems. In many cases, the amount of computation required to find all solutions can be made roughly proportional to the number of solutions.     

Randomized online graph coloring

We study the problem of coloring graphs in an online manner. The only known deterministic online graph coloring algorithm with a sublinear performance function was found by [9.], 319–325). Their algorithm colors graphs of chromatic number χ with no more than (2χn)/log^* n colors, where n is the number of vertices. They point out that the performance can be improved slightly for graphs with bounded chromatic number. For three-chromatic graphs the number of colors used, for example, is O(n log log log n/log log n). We show that randomization helps in coloring graphs online. We present a simple randomized online algorithm to color graphs with expected number of colors O(2^χχ²n^{(χ−2)/(χ−1)}(log n)^1/(χ−1)). For three-colorable graphs the expected number of colors our algorithm uses is . All our algorithms run in polynomial time. It is interesting to note that our algorithm compares well with the best known polynomial time offline algorithms. For instance, the best polynomial time algorithm known for three-colorable graphs, due to [4.] pp. 554–562). We also prove a lower bound of Ω((1/(χ − 1))((log n/(12(χ + 1))) − 1)^χ−1) for the randomized model. No lower bound for the randomized model was previously known. For bounded χ, our result improves even the best known lower bound for the deterministic case: Ω((log n/log log n)^χ−1), due to Noga Alon (personal communication, September 1989).     

Eine Methode zur berechnung sämtlicher Lösungen von Polynomgleichungssystemen

Summary In this paper a numerical method is given to compute all solutions of systemsT ofn polynomial equations inn unknowns on the only premises that the sets of solutions of these systems are finite. The method employed is that of embedding, i.e. the systemT is embedded in a set of systems which are successively solved, starting with one having solutions easily to compute and proceding toT in a finite series of steps. An estimation of the number of steps necessary is given. The practicability of the method is proved for all systemsT. Numerical examples and results are contained.

Diese Arbeit ist eine Zusammenfassung der Ergebnisse der Dissertation, die der Verfasser an der Johannes-Kepler-Universität Linz und der Technischen Universität München unter der Betreuung von Prof. Dr. Hansjörg Wacker angeferetigt hat. 2. Begutachter: Prof. Dr. Manfred Feilmeier     

On factoring parametric multivariate polynomials

This paper presents a new algorithm for the absolute factorization of parametric multivariate polynomials over the field of rational numbers. This algorithm decomposes the parameters space into a finite number of constructible sets. The absolutely irreducible factors of the input parametric polynomial are given uniformly in each constructible set. The algorithm is based on a parametric version of Hensel's lemma and an algorithm for quantifier elimination in the theory of algebraically closed field in order to reduce the problem of finding absolute irreducible factors to that of representing solutions of zero-dimensional parametric polynomial systems. The complexity of this algorithm is single exponential in the number n of the variables of the input polynomial, its degree d w.r.t. these variables and the number r of the parameters.     

Algebraic Order Bounded Disjointness Preserving Operators and Strongly Diagonal Operators

Let T be an order bounded disjointness preserving operator on an Archimedean vector lattice. The main result in this paper shows that T is algebraic if and only if there exist natural numbers m and n such that n ≥ m, and T^n!, when restricted to the vector sublattice generated by the range of T^m, is an algebraic orthomorphism. Moreover, n (respectively, m) can be chosen as the degree (respectively, the multiplicity of 0 as a root) of the minimal polynomial of T. In the process of proving this result, we define strongly diagonal operators and study algebraic order bounded disjointness preserving operators and locally algebraic orthomorphisms. In addition, we introduce a type of completeness on Archimedean vector lattices that is necessary and sufficient for locally algebraic orthomorphisms to coincide with algebraic orthomorphisms.     

Boundary element preconditioners for a hypersingular integral equation on an interval

We propose an almost optimal preconditioner for the iterative solution of the Galerkin equations arising from a hypersingular integral equation on an interval. This preconditioning technique, which is based on the single layer potential, was already studied for closed curves [11,14]. For a boundary element trial space, we show that the condition number is of order (1 + | log h _min|)², where h _min is the length of the smallest element. The proof requires only a mild assumption on the mesh, easily satisfied by adaptive refinement algorithms.     

A fast algorithm for scalar Nevanlinna-Pick interpolation

Summary In this paper, we derive a fast algorithm for the scalar Nevanlinna-Pick interpolation. Givenn distinct pointsz _i in the unit disk |z|<1 andn complex numbersw _i satisfying the Pick condition for 1in, the new Nevanlinna-Pick interpolation algorithm requires onlyO(n) arithmetic operations to evaluate the interpolatory rational function at a particular value ofz, in contrast to the classical algorithm which requiresO(n ²) arithmetic operations to compute the so-called Fenyves array (which is inherent in the classical algorithm). The new algorithm bypasses the generation of the Fenyves array to speed up the computation, and also yields a parallel scheme requiring onlyO(logn) arithmetic operations on a concurrent-read, exclusive-write parallel random access machine withn processors. We must remark that the rational functionf(z) computed by the new algorithm is one degree higher than the function computed by the classical algorithm.Supported in part by the US Army Research Office Grant No. DAAL03-91-G-0106     

On the positivity of certain Cotes numbers

It is shown that the Cotes numbers are nonnegative for some interpolatory quadratic rules with nodes at the zeros of the ultraspherical polynomialsC _n , when integrating with respect to the weight functions w_µ(x)=(1–x²)^µ–1/2.     

A fast ‘Monte-Carlo cross-validation’ procedure for large least squares problems with noisy data

Summary We propose a fast Monte-Carlo algorithm for calculating reliable estimates of the trace of the influence matrixA involved in regularization of linear equations or data smoothing problems, where is the regularization or smoothing parameter. This general algorithm is simply as follows: i) generaten pseudo-random valuesw ₁, ...,w _n , from the standard normal distribution (wheren is the number of data points) and letw=(w ₁, ...,w _n ) ^T , ii) compute the residual vectorw–A w, iii) take the normalized inner-product (w ^T (w–A w))/(w ^T w) as an approximation to (1/n)tr(I–A ). We show, both by theoretical bounds and by numerical simulations on some typical problems, that the expected relative precision of these estimates is very good whenn is large enough, and that they can be used in practice for the minimization with respect to of the well known Generalized Cross-Validation (GCV) function. This permits the use of the GCV method for choosing in any particular large-scale application, with only a similar amount of work as the standard residual method. Numerical applications of this procedure to optimal spline smoothing in one or two dimensions show its efficiency.     

On additive Schwarz preconditioners for sparse grid discretizations

Summary Based on the framework of subspace splitting and the additive Schwarz scheme, we give bounds for the condition number of multilevel preconditioners for sparse grid discretizations of elliptic model problems. For a BXP-like preconditioner we derive an estimate of the optimal orderO(1) and for a HB-like variant we obtain an estimate of the orderO(k ² ·2 ^k/2 ), wherek denotes the number of levels employed. Furthermore, we confirm these results by numerically computed condition numbers.     

On Number of Occurrences of Success Runs of Specified Length in a Higher-Order Two-State Markov Chain

Let X^-m+1, X^-m+2,..., X⁰, X¹, X²,..., Xⁿ be a time-homogeneous {0, 1}-valued m-th order Markov chain. The probability distributions of numbers of runs of "1" of length k (k m) and of "1" of length k (k < m) in the sequence of a {0, 1}-valued m-th order Markov chain are studied. There are some ways of counting numbers of runs with length k. This paper studies the distributions based on four ways of counting numbers of runs, i.e., the number of non-overlapping runs of length k, the number of runs with length greater than or equal to k, the number of overlapping runs of length k and the number of runs of length exactly k.     

Study of linear information for classes of polynomial equations

Summary We study linear sequential (adaptive) information for approximating zeros of polynomials of unbounded degree and establish a theorem on constrained approximation of smooth functions by polynomials.For a positive we seek a pointx ^* such that|x ^* – _p | , where _p is a zero of a real polynomialp in the interval [a, b]. We assume thatp belongs to the classF ₁ of polynomials of bounded arbitrary seminorm and having a root in [a, b] or to the classF ₂ of polynomials which are nonpositive ata, nonnegative atb and have exactly one simple zero in [a, b]. The information onp consists ofn sequential (adaptive) evaluations of arbitrary linear functionals. The pointx ^* is constructed by means of an algorithm which is an arbitrary mapping depending on the information onp. We show that there exists no information and no algorithm for computingx ^* for everyp fromF ₁, no matter how large the value ofn is. This is a stronger result than that obtained by us for smooth functions.For the classF ₂ we can find a pointx ^* for arbitraryp and. Anoptimal algorithm, i.e., an algorithm with the smallest error, is thebisection of the smallest known interval containing the root ofp. We also exhibitoptimal information operators, i.e., the linear functionals for which the error of an optimal algorithm that uses them is minimal. It turns out that in the class of nonsequential (parallel) information, i.e., when the functionals are given simultaneously, optimal information consists of the evaluations of a polynomial atn-equidistant points in [a, b]. In the class of sequential continuous information, optimal information consists of evaluations of a polynomial atn points generated by thebisection method. To prove this result we establish a theorem on constrained approximation of smooth functions by polynomials. More precisely, we prove that a smooth function can be arbitrarily well uniformly approximated by a polynomial which satisfies constrains given byn arbitrary continuous linear functionals.Our results indicate that the problem of finding an -approximation to a real zero of a real polynomial (of unknown degree) is essentially of the same difficulty as the problem of finding an -approximation to a zero of an infinitely differentiable function.     

Multivariate Polynomial Minimization and Its Application in Signal Processing

We make a conjecture that the number of isolated local minimum points of a 2n-degree or (2n+1)-degree r-variable polynomial is not greater than n ^r when n 2. We show that this conjecture is the minimal estimate, and is true in several cases. In particular, we show that a cubic polynomial of r variables may have at most one local minimum point though it may have 2^r critical points. We then study the global minimization problem of an even-degree multivariate polynomial whose leading order coefficient tensor is positive definite. We call such a multivariate polynomial a normal multivariate polynomial. By giving a one-variable polynomial majored below a normal multivariate polynomial, we show the existence of a global minimum of a normal multivariate polynomial, and give an upper bound of the norm of the global minimum and a lower bound of the global minimization value. We show that the quartic multivariate polynomial arising from broad-band antenna array signal processing, is a normal polynomial, and give a computable upper bound of the norm of the global minimum and a computable lower bound of the global minimization value of this normal quartic multivariate polynomial. We give some sufficient and necessary conditions for an even order tensor to be positive definite. Several challenging questions remain open.     

Fast inversion of vandermonde-like matrices involving orthogonal polynomials

Let {q} _j ^=0n–1 be a family of polynomials that satisfy a three-term recurrence relation and let {t _k } _k ⁼¹ⁿ be a set of distinct nodes. Define the Vandermonde-like matrixW _n =[w _jk ] _k,j ⁼¹ⁿ ,w _jk =q _j–1(t _k ). We describe a fast algorithm for computing the elements of the inverse ofW _n inO(n ²) arithmetic operations. Our algorithm generalizes a scheme presented by Traub [22] for fast inversion of Vandermonde matrices. Numerical examples show that our scheme often yields higher accuracy than the LINPACK subroutine SGEDI for inverting a general matrix. SGEDI uses Gaussian elimination with partial pivoting and requiresO(n ³) arithmetic operations.Dedicated to Gene H. Golub on his 60th birthdayResearch supported by NSF grant DMS-9002884.     

Polynomial Approximation on Convex Subsets of R n

Let K be a closed bounded convex subset of R ⁿ ; then by a result of the first author, which extends a classical theorem of Whitney there is a constant w _m (K) so that for every continuous function f on K there is a polynomial ϕ of degree at most m-1 so that |f(x)-ϕ(x)|≤ w_m(K) sup _{x,x+mh∈ K} |Δ_h^m(f;x)|. The aim of this paper is to study the constant w _m (K) in terms of the dimension n and the geometry of K . For example, we show that w ₂ (K)≤ (1/2) [ log ₂ n]+5/4 and that for suitable K this bound is almost attained. We place special emphasis on the case when K is symmetric and so can be identified as the unit ball of finite-dimensional Banach space; then there are connections between the behavior of w _m (K) and the geometry (particularly the Rademacher type) of the underlying Banach space. It is shown, for example, that if K is an ellipsoid then w ₂ (K) is bounded, independent of dimension, and w ₃ (K)\sim log n . We also give estimates for w ₂ and w ₃ for the unit ball of the spaces l _p ⁿ where 1≤ p≤∈fty. September 24, 1997. Dates revised: January 18, 1999 and June 10, 1999. Date accepted: June 25, 1999.     

Average errors for zero finding: Lower bounds for smooth or monotone functions

Summary We study zero finding for functions fromC ^r ([0, 1]) withf(0) f(1) < 0 and for monotone functions fromC([0, 1]). We show that a lower bound ⁿ with a constant holds for the average error of any method usingn function or derivative evaluations. Here the average is defined with respect to conditionalr-fold Wiemer measures or Ulam measures, and the error is understood in the root or residual sense. As in the worst case, we therefore cannot obtain superlinear convergence even for classes of smooth functions which have only simple zeros.     

On odd points and the volume of lattice polyhedra

Denote by _n ³ ,n 2, the lattice consisting of all pointsx in ³ such thatnx belongs to the fundamental lattice ³ of points with integer coordinates. Letl _n be the subset of _n ³ consisting of all points whose coordinates are odd multiples of 1/n. The purpose of this paper is to give several new Pick-type formulae for the volume of three-dimensional lattice polyhedra, that is, polyhedra with vertices in ³. Our formulae are in terms of numbers of only thel _n-points belonging to a lattice polyhedronP in contrast to already known formulae which employ numbers of all the _n ³ -points inP. On our way to establishing the formulae we show that the number of points froml _n belonging to a three-dimensional lattice polyhedronP has some polynomiality properties similar to those of the well-known Ehrhart polynomial expressing the number of points of _n ³ inP. The paper contains also some comments on a problem of finding a volume formula which would employ only the setsl _n and which would be applicable to lattice polyhedra in arbitrary dimensions.Research partially supported by KBN Grant 2 P03A 008 10.