An algorithm for the computation of the exponential spline

Summary Procedures for the calculation of the exponential spline (spline under tension) are presented in this paper. The procedureexsplcoeff calculates the second derivatives of the exponential spline. Using the second derivatives the exponential spline can be evaluated in a stable and efficient manner by the procedureexspl. The limiting cases of the exponential spline, the cubic spline and the linear spline are included. A proceduregenerator is proposed, which computes appropriate tension parameters. The performance of the algorithm is discussed for several examples.Editor's Note: In this fascile, prepublication of algorithms from the Approximation series of the Handbook for Automatic Computation is continued. Algorithms are published in ALGOL 60 reference language as approved by the IFIP. Contributions in this series should be styled after the most recently published ones     

Extrapolation applied to certain discretization methods solving the initial value problem for hyperbolic differential equations

Summary The procedurediwiex presented in this paper provides an approximate solution to Cauchy's initial value problem for general hyperbolic systems of first order. The procedurecharex can be applied to the initial value problem for a hyperbolic system of quasi-linear differential equations. This second method is a kind of method of characteristics. It produces a solution for the whole domain of determinancy. Both procedures use extrapolation to the limit. Editor's Note. In this fascile, prepublication of algorithms from the Approximations series of the Handbook for Automatic Computation is continued. Algorithms are published in ALGOL 60 reference language as approved by the IFIP. Contributions in this series should be styled after the most recently published ones     

A method of characteristics solving the initial-boundary value problem of a hyperbolic differential equation of second order

Summary The ALGOL-procedure¹ char2 presented in this paper can be applied to the initial or initial-boundary value problem of a quasilinear hyperbolic differential equation of second order. A method of characteristics is combined with extrapolation to the limit. Thus, the results are very accurate. The same accuracy can also be obtained if the initial values are only piecewise smooth.Editor's Note: In this fascile, prepublication of algorithms from the Approximation series of the Handbook for Automatic Computation is continued. Algorithms are published in ALGOL 60 reference language as approved by the IFIP. Contributions in this series should be styled after the most recently published ones     

Zur bestimmung aller elementarkreise in gerichteten graphen

New algorithms for enumerating all circuits of a directed graph are presented. These algorithms are backtrack algorithms, by which we intended to avoid fruitless computations. The best results give algorithms involving heuristic rules.

To receive numerical comparisons additionally the algorithms of DÖRFLER/MÜHL-BACHER, TIERNAN/SYSLO and BJELKINA were programmed and tested in FORTRAN (CDC 3300) and (or) ALGOL (ICL 4130).     

Divergenzverhalten mehrdimensionaler Shannonscher Abtastreihen

The behaviour of multidimensional Shannon sampling series for continuous functions is examined. A continuous function g ₁∈C ₀ [0,1]² with support in the rectangle [0,1] × [0,?] is indicated in the paper for which the two dimensional Shannon sampling series diverge almost everywhere in the rectangle [0,1] × [?,1]. This shows that the localization principle for Shannon sampling series cannot hold in two dimensions and in higher dimensions. The result solves a problem formulated by P.L. Butzer. Received: 21 December 1995 / Revised version: 5 October 1996     

Computation of the small eigenvalues of a matrix

We present the ALGOL programdeigv which computes the small (in absolute value) isolated eigenvalues and their eigenvectors for a real diagonalizable matrix. Test samples are included.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 80, pp. 167–180, 1978.     

On the Zero-Divergence of Equidistant Lagrange Interpolation

 In 1942, P. Szász published the surprising result that if a function f is of bounded variation on [−1, 1] and continuous at 0 then the sequence of the equidistant Lagrange interpolation polynomials converges at 0 to . In the present note we give a construction of a function continuous on [−1, 1] whose Lagrange polynomials diverge at 0. Moreover, we show that the rate of divergence attains almost the maximal possible rate. (Received 2 February 2000)     

Pointwise Behavior of Double Fourier Series of Functions of Bounded Variation

We extend some recent results of S. A. Telyakovskii on the uniform boundedness of the partial sums of Fourier series of functions of bounded variation to periodic functions of two variables, which are of bounded variation in the sense of Hardy. As corollaries, we obtain the classical Parseval formula, the convergence theorem of the series involving the sine Fourier coefficients, and a lower estimate of the best approximation by trigonometric polynomials in the metric of L in a sharpened version. This research was supported by the Hungarian National Foundation for Scientific Research under Grants TS 044 782 and T 046 192.     

An arsenal of ALGOL procedures for complex arithmetic

This paper contains a complete system of ALGOL procedures which enable arithmetic operations to be carried out upon complex numbers. Further procedures for carrying out the evaluation of certain elementary functions (e.g. ln, exp, sin, ...) of a complex variable are given. Application of these procedures is then illustrated by their use in the computation of the confluent hypergeometric function and the Weber parabolic cylinder function. Procedures relating to the application of the -algorithm to series of complex terms are described. Two integrated series of procedures, relating to Stieltjes typeS-fractions and to corresponding continued fractions respectively, are given. Complete programmes, which illustrate the use of these procedures, may be used for the computation of the incomplete-function, the incomplete-function (of arguments of large and small modulus) and the Weber function.     

A programming technique for recursive procedures

A programming technique is described for ALGOL-like recursive procedures in which parameters and local variables are replaced by variables global to the recursive procedure and declared in a surrounding non-recursive procedure. The stack and time required for execution of a variety of recursive procedures has been determined in the languages ALGOL 60, CORAL 66 and ALGOL 68 both when programmed using this technique and when using parameters. Detailed results are presented for the Ackermann function and for tree manipulation.The global technique gives considerable savings in stack for all recursions investigated. For call-dominated recursions the technique speeds up the execution time in ALGOL 60 and CORAL 66 by about 25%. In ALGOL 68 the parameterless recursive procedure must be declared in the closed-clause which forms the particular-program rather than in a surrounding procedure in order to achieve a similar improvement in execution time.     

A new high order method of regula falsi type for computing a root of an equation

A hybrid method of order five (eight) which uses three (four) function evaluations per step is presented together with an algorithm which ensures global convergence. The method is compared with its closest competitors (among globally convergent methods which do not use derivatives) in a series of numerical examples. An ALGOL procedure of the method is included.     

Rotation number for non-autonomous linear Hamiltonian systems II: The Floquet coefficient

This paper is the second of a two-part series in which we review the properties of the rotation number for a random family of linear non-autonomous Hamiltonian systems. In Part I, we defined the rotation number for such a family and discussed its basic properties. Here we define and study a complex quantity - the Floquet coefficient w - for such a family. The rotation number is the imaginary part of w. We derive a basic trace formula satisfied by w, and give applications to Atkinson-type spectral problems. In particular we use w to discuss the convergence properties of the Weyl M-functions, the Kotani theory, and the gap-labelling phenomenon for these problems.     

RADICALS IN GENERAL Γ-NEAR-RINGS

Abstract

The J ₂ and J ₃ radicals for zerosymmetric Γ-near-rings were recently defined by the author. In the present paper we define the J ₂₍₀₎ and J ₃₍₀₎ radicals for arbitrary Γ-near-rings. These radicals are sirmlar to corresponding ones which were recently defined by Veldsman for near-rings. Let M be a r-near-ring with left operator near-ring L. Then J _κ(0)(L)⁺ = J _{κ (0)} (M), k. = 2,3. If A is an ideal of M, then J _{κ (0)} (A) ? J _{κ (o)}(M) ∩ A, with equality when k = 3 and A is left invariant. J ₃₍₀₎ is a Kurosh-Amitsur radical in the variety of Γ-near-rings.     

Machine dependent programming in common languages

It is suggested that we should distinguish between common programming languages and common solutions to specific problems. A solution may depend on specific machine characteristics even though it is expressed in a common language. It is further suggested that in future common programming languages this should be admitted openly by allowing the programmer to get access to the machine characteristics at hand through Environment Enquiries which are part of the language. Some specific examples of Environment Enquiries are given.An earlier version of this paper was published in ALGOL BULLETIN no. 18, October 1964.     

Optimizing Area and Perimeter of Convex Sets for Fixed Circumradius and Inradius

 In this paper two problems posed by Santaló are solved: we determine the planar convex sets which have maximum and minimum area or perimeter when the circumradius and the inradius are given, obtaining complete systems of inequalities for the cases (A, R, r) and (p, R, r). This work is supported in part by Dirección General de Investigación (MCYT) BFM2001-2871, and by OTKA grants No 31984 and 30012 Received October 15, 2001; revised January 29, 2002     

Minimal Nonsquare <Emphasis Type="Italic">J</Emphasis>-Spectral Factorization,Generalized Bezoutians and Common Zeros for Rational Matrix Functions

The problem that we solve in this paper is to find (square or nonsquare) minimal J-spectral factors of a rational matrix function with constant signature. Explicit formulas for these J-spectral factors are given in terms of a solution of a particular algebraic Riccati equation. Also, we discuss the common zero structure of rational matrix functions that arise from the analysis of nonsquare J-spectral factors. This zero structure is obtained in terms of the kernel of a generalized Bezoutian.     

Order series of labelled posets

Order series of labelled posets are multi-analogues of the more familiar order polynomials; the corresponding multi-analogues of the related representation polynomials are calledE-series. These series can be used to describe the effect of composition of labelled posets on their order polynomials, whence their interest for us. We give a reciprocity theorem forE-series, and show that for an unlabelled poset the form of theE-series depends only upon the comparability graph of the poset. We also prove that theE-series of any labelled poset is a rational power series (in many indeterminates) and give an algorithm for computing it which runs in polynomial time when the poset is strictly labelled and of bounded width. Finally, we give an explicit product formula for theE-series of strictly labelled interval posets.This research was supported by the Natural Sciences and Engineering Research Council of Canada under operating grant #0105392.     

Integration over a simplex,truncated cubes,and Eulerian numbers

Summary A method of integrating a function over a simplex is described in which (i) the simplex is first transformed into a right-angled isosceles simplex; (ii) this simplex is dissected into small cubes and truncated cubes; (iii) the integration over the truncated cubes is performed by the centroid method or by Stroud's method, and this requires the use of formulae for the moments of a truncated cube. These formulae are developed and are expressed in terms of Eulerian numbers. In the special case when the truncated cube is itself a right-angled isoceles simplex a new algorithm is given, depending on the discrete Fourier transform, for calculating the moments as polynomials inn wheren is the dimensionality.     

Regular closure operators

In an E,M-categoryX for sinks, we identify necessary conditions for Galois connections from the power collection of the class of (composable pairs) of morphisms inM to factor through the lattice of all closure operators onM, and to factor through certain sublattices. This leads to the notion ofregular closure operator. As one byproduct of these results we not only arrive (in a novel way) at the Pumplün-Röhrl polarity between collections of morphisms and collections of objects in such a category, but obtain many factorizations of that polarity as well. (One of these factorizations constituted the main result of an earlier paper by the same authors). Another byproduct is the clarification of the Salbany construction (by means of relative dominions) of the largest idempotent closure operator that has a specified class ofX-objects as separated objects. The same relation that is used in Salbany's relative dominion construction induces classical regular closure operators as described above. Many other types of closure operators can be obtained by this technique; particular instances of this are the idempotent and modal closure operators that in a Grothendieck topos correspond to the Grothendieck topologies.Dedicated to Professor Dieter Pumplün, on his 60th birthdayResearch partially supported by the Faculty of Arts and Sciences, University of Puerto Rico, Mayagüez Campus during a sabbatical visit at Kansas State University.