We address the view about using the Turing Machine model and the real number model for solving continuous scientific problems. Furthermore we will argue that the Turing Machine is the wrong model of computation for the continuous problems of science.

The information-based study of the optimal solution of large linear systems is initiated by studying the case of Krylov information. Among the algorithms that use Krylov information are minimal residual, conjugate gradient, Chebyshev, and successive approximation algorithms. A "sharp" lower bound on the number of matrix-vector multiplications required to compute an å-approximation is obtained for any orthogonally invariant class of matrices. Examples of such classes include many of practical interest such as symmetric matrices, symmetric positive definite matrices, and matrices with bounded condition number. It is shown that the minimal residual algorithm is within at most one matrix-vector multiplication of the lower bound. A similar result is obtained for the generalized minimal residual algorithm. The lower bound is computed for certain classes of orthogonally invariant matrices. How the lack of certam properties (symmetry, positive definiteness) increases the lower bound is shown. A conjecture and a number of open problems are stated.

This note proposes a statistical perturbation scheme to protect a statistical database against compromise. The proposed scheme can handle the security of numerical as well as nonnumerical sensitive fields. Furthermore, knowledge of some records in a database does not help to compromise unknown records. We use Chebyshev's inequality to analyze the trade-offs among the magnitude of the perturbations, the error incurred by statistical queries, and the size of the query set to which they apply. We show that if the statistician is given absolute error guarantees, then a compromise is possible, but the cost is made exponential in the size of the database.

Let $F(x) = f_1 x + f_2 x^2 + \cdots $ be a formal power series over a field $\Delta $ Let $F^{[0]} (x) = x$ and for $q = 1,2, \cdots $ , define $F^{[q]} (x) = F^{[q - 1]} (F(x))$. The obvious algorithm for computing the first n terms of $F^{[q]} (x)$ is by the composition analogue of repeated squaring. This algorithm has complexity about $\log _2 q$ times that of a single composition. Brent showed that the factor $\log _2 q$ can be eliminated in the computation of the first n terms of $(F(x))^q $ by a change of representation, using the logarithm and exponential functions. We show the factor $\log _2 q$ can also be eliminated for the composition problem, unless the complexity of composition is quasi-linear. $F^{[q]} (x)$ can often, but not always, be defined for more general q. We give algorithms and complexity bounds for computing the first n terms of $F^{[q]} (x)$ whenever it is defined. We conclude the paper with some open problems.

An optmaal convergence condmon for Newton ~teratmn m a Banach space ts estabhshed It ~s shown that there exist problems for whtch the ~teraUon converges but the complextty ts unbounded Thus for actual computation convergence ~s not enough What stronger condmon must be unposed to also assure "good complextty" ~s shown KEY WORDS AND PHRASES Newton ~teratton, operator equations, optunal algontlun, convergence, complexity CR CATEGORIES 5 15, 5 25 IntroductwnNumerous papers have analyzed sufficient conditions for the convergence of algonthms for the solution of nonlinear problems.In addRion to convergence, we consider another fundamental question.What stronger conditions must be imposed to assure "good complexity?"This is deafly one of the crucial issues (m addmon to stability) if one is interested in actual computation.We beheve it is also a most interesting theoretical quesUon.We consider Newton iteration for a simple zero of a nonlinear operator in a Banach space of finite or infmite dimension.We establish the opUmal radius of the ball of convergence with respect to a certain functional.There exist problems where the iteration converges but the complexity increases logarithmically to infinity as the initial iterate approaches the boundary of the ball of convergence.(This phenomenon does not occur in the Kantorovich theory of operator equations; see Section 3.) We estabhsh the optimal radius of the ball of good complexity.In this paper we limit ourselves to the important case of Newton iteration.In other papers [8-10] we study optimal convergence and complexRy for classes of iterations.We summarize the results of this paper.Definitions and theorems concerning the optimal ball of convergence are given in Section 2. We conclude this section by giving conditions under which the radius of the ball of convergence is a constant fraction of the radius of the ball of analytioty of the operator.Complexity of Newton iteration ~s studied in Secuon 3. We show that Newton iteration may converge but have arbitrarily high complexity and conjecture that thts is a general phenomenon.We establish the radms of the ball of good complexity as well as a lower bound on the complexity of Newton iteration. Convergence of Newton IterationWe consider the solution of the nonlinear equation Permission to copy wRhout fee all or part of this material ~s granted prowded that the copies are not made or distributed for direct ccommercml advantage, the ACM copyright notice and the title of the publicatton and its date appear, and nottce ts given that copying Is by permtsslon of the AssocmUon for Computmg Machinery To copy otherwtse, or to repubhsh, reqmres a fee and/or speofic permlsston This research was supported m part by the Nauonal Science Foundation under Grant MCS75-222-55 and the Office of Naval Research under Contract N0014-76-C-0370,

The expansions of algebraic functions can be computed "fast" using the Newton Polygon Process and any "normal" iteration Let M(I) be the number of operations sufficient to multiply two/thdegree polynomials It is shown that the first N terms of an expansion of any algebraic function defined by an nth-degree polynomial can be computed in O(nM(N)) operations, while the classical method needs O(N ~) operations Among the numerous apphcatlons of algebraic functions are symbolic mathematics and combinatorial analysis Reversion, reciprocation, and nth root of a polynomial are all special cases of algebraic functions

Iterative methods for the solution of tridiagonal systems are considered, and a new iteration is presented, whose rate of convergence is comparable to that of the optimal two-cyclic Chebyshev iteration but which does not require the calculation of optimal parameters. The convergence rate depends only on the magnitude of the elements of the tridiagonal matrix and not on its dimension or spectrum. The theory also has a natural extension to block tridiagonal systems. Numerical experiments suggest that on a parallel computer this new algorithm is the best of the iterative algorithms considered.

The state of the art in polynomial zerofinding algorithms and programs is briefly summarized, with emphasis on the principles for testing such programs.The authors view testing as requiring four stages: (1) testing program robustness, (2) testing for convergence difficulties, (3) testing for specific weakness of the algorithms, (4) assessment of program performance by statistical testing.It is emphasized that the statistical testing must be done with care.There are many ways to generate "random" polynomials, b r t two classes of random polynomials which have been widely used are of only limited usefulness in terms of evaluating reliability or performance because they produce polynomials with very similar characteristics.Classes of random polynomials which should be used are discussed.

The problem is to calculate a simple zero of a nonlinear function ƒ by iteration. There is exhibited a family of iterations of order 2 n -1 which use n evaluations of ƒ and no derivative evaluations, as well as a second family of iterations of order 2 n -1 based on n — 1 evaluations of ƒ and one of ƒ′. In particular, with four evaluations an iteration of eighth order is constructed. The best previous result for four evaluations was fifth order. It is proved that the optimal order of one general class of multipoint iterations is 2 n -1 and that an upper bound on the order of a multipoint iteration based on n evaluations of ƒ (no derivatives) is 2 n . It is conjectured that a multipoint iteration without memory based on n evaluations has optimal order 2 n -1 .

A family of new algorithms is given for evaluating the first m derivatives of a polynomial. In particular, it is shown that all derivatives may be evaluated in 3 n - 2 multiplications. The best previous result required 1/2 n ( n + 1) multiplications. Some optimality results are presented.

The theory of optimal algorithmic processes is part of computational complexity. This paper deals with analytic computational complexity. The relation between the goodness of an iteration algorithm and its new function evaluation and memory requirements are analyzed. A new conjecture is stated.

This paper presents an elementary treatment of the theory of subresultants, and examines the relationship of the subresultants of a given pair of polynomials to their polynomial remainder sequence as determined by Euclid's algorithm.Two important versions of Euclid's algorithm are discussed.The results are essentially the same as those of Collins, but the presentation is briefer, simpler, and somewhat more general.

MERCURY is a computer-aided system for the selective distribution of Bell Telephone Laboratories technical reports to employees. MERCURY is based on the idea that the job of distribution should be divided between the author and the reader with each performing that part of the job which he does best. The author is asked to describe the interests of the readers to whom his report should be sent. The reader is asked to described the reports that he wishes to receive. The descriptions are made from a small structured vocabulary. The matching of report to reader and the printing of address labels is done by computer.

Some possible combinations of courses