Advances on Computer Mathematics and Its Applications

The following sections are included:

• Foreword

• Contents

We consider the application of several log barrier methods to some test problems that are derived from nonlinearly constrained optimization calculations in only 2 or 4 variables, where each constraint is replaced by several supporting tangent planes. Thus we investigate the efficiency of the methods for up to 10000 linear constraints, our conclusions being drawn from numerical results. The algorithms include the classical log barrier method, Karmarkar's original algorithm and Polyak's shifted log barrier method that employs estimates of Lagrange multipliers. We recommend the use of line searches along directions that are generated by the Newton–Raphson formula. Our results expose some weaknesses of the methods. Therefore they may be helpful to the development of new algorithms that are particularly suitable for semi-infinite programming calculations.

An algorithm for strictly convex quadratic programming is presented. At a dual feasible point that is the solution of the quadratic programming problem for a given active set, several violated constraints are added to the active set for the calculation of a step direction. The dual analogue of Goldfarb's sufficient conditions for simultaneous multiple constraint dropping in feasible point methods is applied on the expense of little additional work compared to that of the usual approach where one constraint at a time is treated. Since dual feasibility corresponding to the enlarged active set may be violated, we show how to drop constraints in order to regain it.

This paper is a report of recent developments concerning the theory and application of : (i) The well-known Bergman kernel method for the conformal mapping of simply-connected domains, (ii) A closely related orthonormalization method for the conformal mapping of multiply-connected domains.

This paper contains a description of a set of FORTRAN subroutines for the accurate computation of the zeros and turning points of the Bessel functions of the first kind.

We describe a class of step-by-step methods for the numerical solution of delay-integro-differential equations of the form

We survey some stability and convergence results concerning approximation of a semigroup e^tA in a Banach space by operators of the form r(kA)ⁿ, nk = t, where r is an A–acceptable rational function. In particular, we present a recent result concerning stability in the case e^tA is analytic and |r(∞)| = 1.

We consider the initial– and boundary–value problem for the Nonlinear (cubic) Schrödinger Equation posed with zero Dirichlet boundary conditions on a bounded domain Ω in R^d, d = 1,2, o 3. We discretize the problem in space by a standard Galerkin–finite element method and in the temporal variable by Crank–Nicolson type and also by higher order, algebraically stable, implicit Runge–Kutta procedures. We review the available theoretical results on error estimates for these schemes with particular emphasis on the question of possible temporal order reduction on general domains. Time stepping with the implicit Runge–Kutta schemes requires solving a nonlinear system of equations at each time step. We analyze Newton's method for solving these nonlinear systems and show how modified Newton schemes may be applied to decouple and solve them in efficient ways, especially effective for parallel implementation. Finally, we show how such fully discrete schemes may be applied with adaptive space and time meshes to approximate radial solutions of the nonlinear Schrödinger equation for d = 2 and 3, which blow up at the origin in finite time, and present the results of relevant blow–up rate calculations.

Considerable effort has been expanded in the last few years in developing numerical methods for Hamiltonian ordinary differential equations, focusing on algorithms that maintain symplectic structure. Specific Runge–Kutta processes emerged in this context as possibly the most promising general-purpose methods. Unfortunately, such methods are computationally expensive to implement. In the present paper we explore ways and means of designing Runge–Kutta processes that are considerably cheaper computationally, while retaining symplecticity. This is done by marrying the technique of perturbed collocation, due to Nørsett and Wanner [13], with the symplecticity test of Sanz-Serna [15].

The well-known Euclid's algorithm is presented as a general iterative method (the E-algorithm) for solving a wide class of linear problems and its relationship to known accelerated implicit and explicit iterative schemes as Richardson, Chebychev and Conjugate Gradient-type methods is given. Some computational work estimates of the E-algorithm are also presented.

A mixed variable finite element method is used for the derivation of an efficient iterative method for nonlinear diffusion problems. The formulation has two advantages as compared to classical finite element methods:

(i) updating of the material coefficients is simplified

(ii) the discrete approximation is much more accurate for problems with (almost) discontinuous coefficients where the discontinuity occurs in the interior of the elements.

Numerical tests with various iterative methods such as Picard's method and Newton's method and with various preconditioning techniques are performed and compared.

Generalized stability of difference method for nonlinear initial value problems is proposed. Such stability implies the convergence with some reasonable conditions. As an example, a conservative scheme is given for RLW equation. The generalized stability is analyzed, from which the convergence follows. The relation between the stability and the conservation is also discussed.

An exponentially fitted Petrov-Galerkin, non-conforming finite element method for a stationary singularly perturbed problem in two dimensions is presented. This method is based on the formulation of a discrete bilinear form. Existence, uniqueness and stability of the approximate solution are proved with respect to a discrete energy norm and an error bound is given for the approximate solution which is independent of the small parameter ε. The associated linear system is structurally symmetric and can be transformed into a symmetric and positive-definite M–matrix. Numerical results are given which show that the method is superior to classical finite element methods.

In this paper we describe the technique of obtaining high resolution, second order, TVD scalar difference schemes. We propose an approach of extending this technique to systems of equations. A class of limiters is presented which includes a discontinuous limiter due to the author, and various limiters are compared numerically.

New parallel algorithms are proposed for the solution of large linear systems of tridiagonal equations which occur repeatedly in the numerical solution of partial differential equations. The extensions to block tridiagonal linear systems are also discussed.

A class of Approximate Inverse Matrix (AIM) algorithmic methods, based on the concept of "root-free" sparse factorization procedures, is introduced for computing explicitly approximate inverses of large sparse symmetric matrices of irregular structure, without inverting the decomposition factors. Explicit first and second-order semi-direct methods, in conjuction with modified forms of the AIM techniques, are presented for solving numerically large finite-element systems on multiprocessor systems. Application of the new methods on a 2D elliptic boundary-value problem is discussed and numerical results are given.

We present a fundamental set of requirements for Problem Solving Environments (PSE) for solving elliptic PDE problems on parallel computers. We propose a design that meets these requirements and defines the architecture of a full PSE, a system that contains most of the necessary components. The system is designed so that it interacts intelligently with both its environment and the user and so that it finds and uses the "best" available solution, for the specific computational resources. As a particular reduced version we obtain "EUCLID", a small, economic, flexible and efficient PSE, that can operate on small platforms and can be used for the study of parallel PDE algorithms as well as for research on PDEs. We also discuss the use of EUCLID with virtual parallel environments and we give details on the present state of implementation of the EUCLID system.

In this study a subdomain-by-subdomain (SBS) preconditioner is developed in conjunction with the conjugate gradient method for the solution of large problems resulting from the application of the finite element method. The proposed technique is based on a multi-element group partitioning of the entire domain. The approximate inverse of the global coefficient matrix, which acts as a preconditioner, is expressed by a second-order truncated Neumann series where an additive composition of the matrix by its subdomain contributions is achieved. An important feature of this subdomain preconditioner is its local additive nature which is susceptible to parallelization.

Factorisation of long integers is a key issue in cryptographic applications and there has been much research in the field during recent years. In this paper we describe several of the most important integer factorisation algorithms; we start with the classical trial division and Fermat's algorithms, then we describe Pollard's and the Elliptic Curve probabilistic methods and, finally, the family of quadratic sieve algorithms. Possible uses of parallelism, both at the high and low level of these algorithms, are presented.

In this paper we first give a survey that describes the reductions between several fundamental parallel graph problems. Then, we examine the possibility of designing simple and practical sequential algorithms from parallel ones. Interestingly enough, we show how to design fast (in fact optimal) sequential algorithms from the optimal parallel algorithms for a graph theoretic problem that arizes often in many areas including Economics and Operations Research In particular, we give two optimal algorithms that solve the vertex updating for a minimum spanning tree problem. Finally, we show how these algorithms can be used to obtain incremental algorithms for computing the minimum spanning tree (MST) of a graph. The MST algorithms are optimal for dense graphs.

As computers become more powerful, they become useful tools to aid in research tasks. The availability of high speed high resolution graphics devices has had a significant impact on tasks which are visual in nature. We describe applications of visualization to the modeling of topological surfaces and the animation of geometric algorithms.

A new formulation for free boundary problems in phase transition phenomena including volume changing is proposed. This is an extension of classical Stefan formulation to consider volume changing induced by the difference of density in each phase. With this formulation in three dimension, these phenomena are simulated in the axisymmetric cases reduced into two dimension by the fixed domain method, and in the flat cases reduced into one dimension by the enthalpy method.

For given univariate function values contaminated by random errors, the least squares smoothing subject to non-negative divided differences of order m may be required. We overview a stable, two phase, approach. First calculate an initial approximation that comes close to the optimum. Then use this approximation as the starting point of a quadratic programming algorithm that completes the calculation of the optimum in the dual space. Its implementation utilizes duality, QR factorization and updating procedures that preserve the banded matrices that occur. A computer program has been written and some numerical results illustrate the method.

This paper is part of a research project aiming at a general methodology for solving stochastic dynamic two-stage linear-quadratic games. The well-known problem in the strategic trade literature, whereby the domestic government seeks an optimal subsidy for a domestic firm that along with a foreign firm produces a homogeneous product for export to a third country, is used as a vehicle to illustrate the solution methodology. In particular, it is shown that the matrix polynomial associated with the characteristic equations of the Euler conditions that describe the equilibrium of the two-stage game can have a stable factorization. This factorization makes it possible to obtain an analytic representation of the equilibrium. Although the results of this paper are derived only with explicit reference to the time-inconsistent equilibrium of the game, most of them apply to the time-consistent equilibrium as well.