Estimating the quality of computational algorithms — Part 1

Computational algorithms for approximate calculation of the mapping $\text{A:X → Y}$ on some element $\text{f}$ of the compactum $\text{X}$ are considered, where $\text{A}$ is a one-to-one continuous mapping. Topology on $\text{X}$ and $\text{Y}$ is set by imbedding them into some Banach spaces. The relation between $\text{?(N; X)}$ and $\text{?(N);Y}$ plays the main role in the problems concerning the construction of such computational algorithms. Here $\text{?(N);X)}$ is a function reciprocal to the ?-entropy of the compactum $\text{X}$. The computational algorithm $\text{U}$ is characterized first of all by the volume of the input data $\text{N}$ and that accuracy ? with which elements $\text{g}$ on the output are defined. If $\text{N}$ is given (but under condition that a table of any $\text{f}$ is admissible), then inf $\text{? = ?}{}_1\text{(N)}$ exists.For the given concrete algorithm the quantity $\text{?/?}{}_1\text{(N)}$ characterizes its qualities and is one of the most important characteristics of the algorithm. In this paper some of the simplest current algorithms are analyzed, and their quality is determined as well. A number of recommendations relative to the questions of the construction of computational algorithms is proposed.     

Some results on addition/subtraction chains

Let ?(n) (respectively $\text{?}$(n)) be the length of the shortest addition chain respectively addition/subtraction chain for n. We shall present several results on $\text{?}$(n). In particular, we determine $\text{?}$(n) for all n satisfying $\text{s}\text{(}\text{n}\text{) ? 3}$ and show $\text{?}\text{log n}\text{? + 2 ?}\text{?}\text{(}\text{n}\text{)}$ for all n satisfying $\text{s}\text{(}\text{n}\text{) ? 3}$, where $\text{s}\text{(}\text{n}\text{)}$ is the extended sum of digits of n. These results are based on analogous results for ?(n) and on the following two inequalities: |n| ? 2^d?1F_f+3 < 2^k?b and $\text{f + b}\text{?}\text{log}\text{s}\text{(n)}$ for a chain of length k = d + f + b with d doublings, f short steps, and b back steps for n. Moreover, we show that the difference $\text{?(}\text{n}\text{)?}\text{?}\text{(}\text{n}\text{)}$ (respectively $\text{?}\text{(}\text{n}\text{)??}\text{log n}\text{?}$) can be made arbbitrarily large. In addition, we prove that $\text{?}\text{(}\text{m}\text{) ?}\text{?}\text{(?}\text{m}\text{) ?}\text{?}\text{(}\text{m}\text{) + 1}\text{for m}\text{> 0}$ and characterize the case $\text{?}\text{(?}\text{m}\text{) =}\text{?}\text{(}\text{m}\text{)}$. Finally, we determine $\text{?}{}_{\mathrm{<mtext>k</mtext>}}\text{(}\text{n}{}_1\text{,…,}\text{n}{}_{\mathrm{k}}\text{)}$, the k-dimensional generalization of $\text{?}$, with the help of $\text{?}\text{(}\text{n}{}_1\text{,…,}\text{n}{}_{\mathrm{k}}\text{)}$, the k-element generalization of $\text{?}$.     

One way finite visit automata

A one-way preset Turing machine with base L is a nondeterministic on-line Turing machine with one working tape preset to a member of L. FINITEREVERSAL($\text{L}$) (FINITEVISIT ($\text{L}$)) is the class of languages accepted by one-way preset Turing machines with bases in $\text{L}$ which are limited to a finite number of reversals (visits). For any full semiAFL $\text{L}$, FINITEREVERSAL ($\text{L}$) is the closure of $\text{L}$ under homomorphic replication or, equivalently, the closure of $\text{L}$ under iteration of controls on linear context-free grammars while FINITEVISIT ($\text{L}$) is the result of applying controls from $\text{L}$ to absolutely parallel grammars or, equivalently, the closure of $\text{L}$ under deterministic two-way finite state transductions. If $\text{L}$ is a full AFL with $\text{L}$ ≠ FINITEVISIT($\text{L}$), then FINITEREVERSAL($\text{L}$) ≠ FINITEVISIT($\text{L}$). In particular, for one-way checking automata, k + 1 reversals are more powerful than k reversals, k + 1 visits are more powerful than k visits, k visits and k + 1 reversals are incomparable and there are languages definable within 3 visits but no finite number of reversals. Finite visit one-way checking automaton languages can be accepted by nondeterministic multitape Turing machines in space log₂n. Results on finite visit checking automata provide another proof that not all context-free languages can be accepted by one-way nonerasing stack automata.     

On some bounded semiAFLs and AFLs

Goldstine [8] has conjectured that not all context-free languages are contained in $\text{F}$_∩($\text{B}$)—the smallest AFL closed under intersection and containing all bounded languages. We prove this by showing that the linear context-free language pal is not in $\text{F}$_∩($\text{B}$). Inclusion relations among various subfamilies of $\text{F}$∩($\text{B}$) as well as their closure properties are studied. It is shown that all languages defined by polynomials whose coefficients are natural numbers are in $\text{M}$_∩(prod)—the smallest intersection-closed semiAFL containing the language $\text{prod}\text{=a}{}^{\mathrm{m}}\text{b}{}^{\mathrm{n}}\text{c}{}^{\mathrm{mn}}\text{s|m,n in N}$. This implies that the corresponding full semiAFL$\text{M}\text{?}$_∩ (prod) is equal to the smallest intersection-closed full semiAFL containing all recursively enumerable bounded languages. An analogous result for all bounded languages is also obtained. Since pal is not in$\text{M}\text{?}$_∩(prod), it follows that $\text{M}\text{?}$^lin_∩(prod) is a semiAFL closed under intersection and linear-erasing homomorphism but is not closed under Kleene⁺, homomorphism, or nonerasing homomorphic replication. This solves a problem considered by Book and Greibach [2]. Finally, nonprincipality of some semiAFLs and AFLs is established. As a consequence, we solve a problem of Ginsburg [6].     

Graph theoretic characterization of G-schemes and TL-schemes

The $\text{G}$-schemes are a class of structured flowchart schemes defined algebraically by Elgot in [1]. Bloom and Tindell [2] gave a graph theoretic characterization of the biaccessible $\text{G}$-schemes, i.e. those in which every vertex is on a path from begin to exit. We give here a graph theoretic characterization of the entire class of $\text{G}$-schemes, and also of a smaller and simpler class, the $\text{T}$$\text{L}$-schemes of [5].     

Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials

We improve some lower bounds which have been obtained by Strassen and Lipton. In particular there exist polynomials of degree n with 0–1 coefficients that cannot be evaluated with less than $\text{n}\text{/(4}\text{log}\text{n)}$ nonscalar multiplications/divisions. The evaluation of p(x) $\text{∑}\text{δ=0}\text{n}\text{e}{}^{\mathrm{<mtext>2\pi i</mtext><mtext>2\delta </mtext>}}\text{x}{}^{\mathrm{\delta }}$ requires at least $\text{n}\text{(12}\text{log}\text{n)}$ multiplications/divisions and at least $\text{n/(8}\text{log}\text{n)}$ nonscalar multiplications/divisions. We specify polynomials with algebraic coefficients that require $\text{1}\text{2}\text{n}$ multiplications/divisions.     

System identification in nonlinear structural seismic dynamics

This paper deals with the development of efficient identification methods for the determination of parameters associated with the nonlinear response of structural systems subject to seismic conditions. The equation of motion of the system is given by $\text{M}\text{u}\text{?}\text{+ h(/.u, u, a) = p(t)}$, where the external force vector $\text{p}$ and the mass matrix $\text{M}$ are assumed to be known. Also given is an observation vector $\text{w}$, consisting of some or all of the components of $\text{u}$, the vector of the nodal displacements. The vector function $\text{h}$, denoting the restoring forces of the mechanical system, is parametrically given in terms of a constant vector $\text{a}$. Three different methods are presented for the determination of the parameters governing the vector function $\text{h}$. The first one is a direct approach requiring the unknown coefficients to appear linearly in the model equation. The remaining two are based on methods of control and optimization theory, and are exempt from the limitations of the direct method. The relative merits of each approach are discussed and extensive numerical experimentation is presented. Only numerical results for one degree of freedom systems are reported in this paper.     

Minimax design of recursive digital filters

The application of two new algorithms for minimax optimization due to Charalambous and Bandler is investigated. The application is to the problem of finding the coefficients of a recursive digital filter to meet arbitrary specifications of the magnitude or the group delay characteristics. Unlike the original minimax algorithm due to Bandler and Charalambous in which a sequence of least $\text{p}\text{th}$ optimizations as $\text{p}$ tends to infinity is taken, the two new algorithms do not require the value of $\text{p}$ to do this. Instead, a sequence of least $\text{p}\text{th}$ optimization problems is constructed with finite values of $\text{p}$ in the range $\text{1 < p < ∞}$. A criterion is given under which the order of the filter can be increased by growing filter sections. A general computer program has been developed, based on the ideas presented.     

Pattern recognition: The categorical setting

We present in this paper the categorical setting for patterns and pattern recognition, bringing together several of our previous results and unifying the algebraic syntactic-oriented, automata-theoretical, and topological formalisms. After briefly recalling these formalisms and terminology, we first show under which conditions images $\text{I}{}_{\mathrm{\mu }}\text{?}\text{I}$ and deformations δ?Δ can be organized in a category $\text{(}\text{I}\text{,Δ) =}\text{I}{}^{\mathrm{\Delta }}$, and how one can associate with it a recognition category $\text{(}\text{I}\text{,Γ) =}\text{I}$, where Γ is a group of similarities γ?Γ included in Δ. Probes and recognition functions are characterized as being invariant functors of categories, and a particular class of probes—projections—is studied using the notion of retract of a category; this notion is then used to characterize the family ? of patterns. The relationship between $\text{I}$, $\text{I}$^Δ, and ? is described. Further investigation of recognition in $\text{I}$ is performed by exhibiting the practical meaning of retracts along with their lifting properties. Furthermore, the recognition problem associated with the initial deformed image category $\text{I}$^Δ is studied, introducing the skeleton Σ of $\text{I}$^Δ; the role played by retracts is again emphasized. Finally we present the connection between patterns, projections and, skeletons; the link existing between the present formalism and current application; and the topological explanation of the “useful” properties of projections and skeletons. The paper ends by listing some open research problems.     

An iterative method for determining the current-potential curves of a spherical probe in a slightly ionized continuum plasma with 5 ⩽ ρp ⩽ 50, yp < 7

A desk analogue computer has been used to draw normalized curves for positive and negative particle concentrations $\text{(n}{}_{\mathrm{+}}\text{,n}{}_{\mathrm{?}}\text{)}$ and potential $\text{(y)}$ vs the distance from a spherical probe surface for a slightly ionized continuum plasma. The governing equations are three simultaneous differential equations leading to a two-point boundary condition problem. An iterative analogue method has been developed which enables the positive and negative particle currents $\text{(J}{}_{\mathrm{+}}\text{,J}{}_{\mathrm{?}}\text{)}$ to the probe, for particular $\text{y}{}_{\mathrm{p}}\text{< 7}$ and $\text{ρ}{}_{\mathrm{p}}\text{< 50}$, to be found to a numerical accuracy of about 1 digit in the second decimal place.     

Calculation of flow between two rotating coaxial disks by differentiation with respect to an actual parameter

A method which allows to find the dependence of the solution $\text{x(ξ, s)}$ on the parameter $\text{s}$ for a nonlinear boundary value problem will be presented. The calculation of the dependence of $\text{x(ξ, s)}$ on $\text{s}$ is performed in a non-iterative way. The technique is employed to solve a difficult two-point boundary value problem: steady state flow of an incompressible viscous fluid between two rotating coaxial disks.     

Asymptotic properties of minimax trees and game-searching procedures

The model most frequently used for evaluating the behavior of game-searching methods consists of a uniform tree of height h and a branching degree d, where the terminal positions are assigned random, independent and identically distributed values. This paper highlights some curious properties of such trees when h is very large and examines their implications on the complexity of various game-searching methods.If the terminal positions are assigned a WIN-LOSS status with the probabilities P₀ and 1 ? P₀, respectively, then the root node is almost a sure MIN or a sure LOSS, depending on whether P₀ is higher or lower than some fixed-point probability $\text{P1(d)}$. When the terminal positions are assigned continuous real values, the minimax value of the root node converges rapidly to a unique predetermined value $\text{v1}$, which is the $\text{(1 ? P1)-}\text{fractile}$ of the terminal distribution.Exploiting these properties we show that a game with WIN-LOSS terminals can be solved by examining, on the average, $\text{O}\text{[(d)}{}^{\mathrm{<mtext>h</mtext><mtext>2</mtext>}}\text{]}$ terminal positions if positions if $\text{P}{}_0\text{≠ P1}$ and $\text{O}\text{[(}\text{P1}\text{(1 ? P1)}\text{)}{}^{\mathrm{h}}\text{]}$ positions if $\text{P}{}_0\text{= P1}$, the former performance being optimal for all search algorithms. We further show that a game with continuous terminal values can be evaluated by examining an average of $\text{O}\text{[(}\text{P1}\text{(1 ? P1)}\text{)}{}^{\mathrm{h}}\text{]}$ positions, and that this is a lower bound for all directional algorithms. Games with discrete terminal values can, in almost all cases, be evaluated by examining an average of $\text{O}\text{[(d)}{}^{\mathrm{<mtext>h</mtext><mtext>2</mtext>}}\text{]}$ terminal positions. This performance is optimal and is also achieved by the ALPHA-BETA procedure.     

Solution errors in finite element analysis

The development of the finite element method so far indicates that it is a discretization technique especially suited for positive definite, self-adjoint, elliptic systems, or systems with such components. The application of the method leads to the discretized equations in the form of $\text{u}\text{?}\text{=}\text{f(u)}$, where u lists the response of the discretized system at n preselected points called nodes. Instead of explicit expressions, vector function f and its Jacobian f,_u are available only numerically for a numerically given u. The solution of $\text{u}\text{?}\text{=}\text{f(u)}$ is usually a digital computer. Due to finiteness of the computer wordlength, the numerical solution $\text{u}{}_{\mathrm{c}}$ is in general different from u. Let $\text{u}\text{(}\text{x}\text{, t)}$ denote the actual response of the system in continuum at points corresponding to those of u. In the literature. $\text{u}\text{(}\text{x}\text{, t)-}\text{u}$ is called the discretization errors, $\text{u}\text{-}\text{u}{}_{\mathrm{c}}$ the round-off errors, and the s is. $\text{u}\text{(}\text{x}\text{, t)-}\text{u}{}_{\mathrm{c}}$ is called the solution errors. In this paper, a state-of-the-art survey is given on the identification, growth, relative magnitudes, estimation, and control of the components of the solution errors.