Date: Mon, 15 Dec 86 12:15:48 est ================================================== NUMERICAL ANALYSIS TITLES -- Volume 4, Number 3 December 15 1986 ================================================== ##### AACHEN ##### --------------- The following report(s) may be obtained from: Frau Ch. Jarausch Institute for Geometry and Practical Mathematics RWTH-Aachen Templergraben 55 D-5100 Aachen, Fed. Rep. Germany Submitted by: Rolf Jeltsch --------------- %A Bernd Einfeldt %A Ein schneller Algorithmus zur Loesung des %T Riemann Problems %R Report 36 %I Institut for Geometry and Practical Mathematics %C RWTH-Aachen %D May, 1986 %A Wolfgang Mackens %T Some Notes on Block Gauss-Seidel Newton Iterations for the Solution of Sparse Nonlinear Problems %R Report 37 %I Institut for Geometry and Practical Mathematics %C RWTH-Aachen %D July, 1986 %A Rolf Jeltsch %A Klaus Raczek %T Counterexamples to an Order Barrier for Stable Multistep Discretizations of Linear Hyperbolic Equations %R Report 39 %I Institut for Geometry and Practical Mathematics %C RWTH-Aachen %D October 1986 ##### AMSTERDAM ##### --------------- The following report(s) may be obtained from: CENTRE FOR MATHEMATICS AND COMPUTER SCIENCE Postbus 4079 1009 AB Amsterdam The Netherlands (These reports are available on exchange basis for reports publications on corresponding subjects. Please do not send any reprints. Also available from the Sales Department. Prices - subject to change without prior notice - in Dutch currency. Foreign payments are subject to a surcharge per remittance. To order through electronic mail, contact rob@mcvax.uucp.) Taken from the UUCP network. --------------- %A B. P. Sommeijer %A P. J. van der Houwen %A B. Neta %T Symmetric linear multistep methods for second-order differential equations with periodic solutions. %R Report NM-R8501 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 9 %O f 3,90 %A H. Arndt %A P. J. van der Houwen %A B. P. Sommeijer %T Numerical integration of retarded differential equations with periodic solutions. %R Report NM-R8502 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 11 %O f 3,90 %A H. J. J. te Riele %T Computation of all the amicable pairs below 10 %R Report NM-R8503 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 42 %O f 6,30 %A P. J. van der Houwen %A B. P. Sommeijer %T Explicit Runge-Kutta (-Nystrom) methods with reduced phase errors for computing oscillating solutions. %R Report NM-R8504 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 17 %O f 3,90 %A P. W. Hemker %A S. P. Spekreijse %T Multigrid solution of the steady Euler equations. %R Report NM-R8505 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 13 %O f 3,90 %A J. G. Verwer %T Convergence and order reduction of diagonally implicit Runge-Kutta schemes in the method of lines. %R Report NM-R8506 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 15 %O f 3,90 %R Report NM-R8507 %O f 3,90 %A P. W. Hemker %A S. P. Spekreijse %T Multiple grid and Osher's scheme for the efficient solution of the steady Euler equations. %R Report NM-R8507 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 17 %O f 3,90 %A B. P. Sommeijer %T On the economization of explicit Runge-Kutta methods. %R Report NM-R8508 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 17 %O f 3,90 %A P. J. van der Houwen %A B. P. Sommeijer %T Predictor-corrector methods for periodic second-order initial value problems. %R Report NM-R8509 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 17 %O f 3,90 %A P. J. van der Houwen %T Discretization of hyperbolic differential equations with periodic solutions. %R Report NM-R8510 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 5 %O f 3,90 %A F. W. Wubs %T Performance evaluation of explicit shallow-water equations solver on the Cyber 205. %R Report NM-R8511 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 12 %O f 3,90 %A J. Kok %T Two ADA mathematical functions packages for use in real time. %R Report NM-R8512 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 9 %O f 3,90 %R Report NM-R8513 %A J. H. M. ten Thije Boonkkamp %A J. G. Verwer %T On the odd-even hopscotch scheme for the numerical integration of time-dependent partial differential equations. %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 15 %O f 3,90 %R Report NM-R8514 %A P. J. van der Houwen %T Spatial discretization of hyperbolic equations with periodic solutions. %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 15 %O f 3,90 %A J. van de Lune %A H. J. J. te Riele %A D. T. Winter %T On the zeros of the Riemann zeta function in the critical strip, IV. %R Report NM-R8515 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 18 %O f 3,90 %A W. H. Hundsdorfer %T Stability and B-convergence of linearly implicit Runge-Kutta. methods %R Report NM-R8516 %P 16 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %O f 3,90 %A K. Burrage %A W. H. Hundsdorfer %A J. G. Verwer %T A study of B-convergence of Runge-Kutta methods. %R Report NM-R8517 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 15 %O f 3,90 %A W. M. Lioen %T NUMVEC FORTRAN library manual. Chapter: elliptic PDEs : routine: MGZEB. %R Report NM-R8518 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 17 %O f 3,90 %A P. J. van der Houwen %A B. P. Sommeijer %T Reduction of dispersion in hyperbolic difference schemes by adapting the space discretization. %R Report NM-R8519 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 12 %O f 3,90 %A S. P. Spekreijse %T Second order accurate upwind solutions of the 2D steady Euler equations by the use of a defect correction method. %R Report NM-R8520 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 16 %O f 3,90 %A F. W. Wubs %T Stabilization of explicit methods for hyperbolic initial-value problems. %R Report NM-R8521 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 12 %O f 3,90 %A J. G. Blom %A H. Brunner %T The numerical solution of nonlinear Volterra integral equations of the second kind by collocation and iterated collocation methods. %R Report NM-R8522 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 28 %O f 5,10 %A P. W. Hemker %T Defect correction and higher order schemes for the multigrid solution of the steady Euler equations. %R Report NM-R8523 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 14 %O f 3,90 %A M. Louter-Nool %T BLAS on the CYBER 205. %R Report NM-R8524 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 24 %O f 3,90 %A J. M. Sanz-Serna %A J. G. Verwer %A W. H. Hundsdorfer %T Convergence and order reduction of Runge-Kutta schemes applied to evolutionary problems in partial differential equations. %R Report NM-R8525 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1985 %P 12 %O f 3,90 %A S. A. van de Geer %T A new approach to least squares estimation, with applications %R R-8602 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A B. Koren %T Euler flow solutions for a transonic windtunnel section %R R-8601 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A P. W. Hemker %A G. M. Johnson %T Multigrid approaches to the Euler equations %R R-8602 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A W. H. Hundsdorfer %A J. G. Verwer %T Linear stability of the hopscotch scheme %R R-8603 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A P. J. van der Houwen %A B. P. Sommeijer %A K. Strehmel %T On the numerical integration of second-order initial value problems with a periodic forcing function %R R-8604 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A P. J. van der Houwen %A F. W. Wubs %T The method of lines and exponential fitting %R R-8605 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A W. H. Hundsdorfer %T A note on monotonicity of a Rosenbrock method %R R-8606 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A K. Burrage %A W. H. Hundsdorfer %T The order of B-convergence of algebraically stable Runge-Kutta methods %R R-8607 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A J. M. Sanz-Serna %A J. G. Verwer %T Convergence analysis of one-step schemes in the method of lines %R R-8608 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A H. J. J. te Riele %T On the sign of the difference pi(x)-li(x) %R R-8609 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A B. P. Sommeijer %T NUMVEC FORTRAN library manual chapter: parabolic PDEs : routine: BDMG %R R-8610 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A S. P. Spekreijse %T Multigrid solution of monotone second-order discretizations of hyperbolic conservation laws %R R-8611 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A P. J. van der Houwen %A B. P. Sommeijer %T Phase-lag analysis of implicit Runge-Kutta methods %R R-8612 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A E. de Goede %T Stabilization of the Lax-Wendroff methods and a generalized one-step Runge-Kutta method for hyperbolic initial-value problems %R R-8613 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %T NUMVEC FORTRAN library manual chapter: simultaneous linear equations %A W. Hoffmann %A W. M. Lioen %R R-8614 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 5,10 %A J. H. M. ten Thije Boonkkamp %T The odd-even hopscotch pressure correction scheme for the incompressible Navier-Stokes equations %R R-8615 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A B. Koren %T Evaluation of second order schemes and defect correction for the multigrid computation of airfoil flows with steady Euler equations %R R-8616 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A P. J. van der Houwen %A B. P. Sommeijer %A F. W. Wubs %T Analysis of smoothing operators in the solution of partial differential equations by explicit difference schemes %R R-8617 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 %A J. G. Blom %A H. Brunner %T Discretized collocation and iterated collocation for nonlinear Volterra integral equations of the second kind %R R-8618 %I Centre for Mathematics and Computer Science %C Amsterdam, C.W.I. %D 1986 %O f 3,90 ##### ARGONNE NATIONAL LABORATORY ##### --------------- The following report(s) may be obtained from: Jack Dongarra Math and Computer Science Div Argonne National Lab Argonne, Illinois 60439 USA Submitted by: Bill Coughran --------------- %T Aspects of Computational Circuit Analysis %A W. M. Coughran, Jr. %A Eric Grosse %A Donald J. Rose %R AT&T Bell Labs Numerical Analysis Manuscript 86-4 %X A hierarchical formulation of the differential-algebraic systems describing circuit behavior is presented. A number of algorithms that have proven effective are reviewed. These include multidimensional splines that preserve monotonicity, sparse direct and iterative methods for the linear equations, damped-Newton and Newton-iterative techniques for the nonlinear equations, continuation methods, and low-order time- integration formulae. Some aspects of time macromodeling are described. ##### BOEING ##### --------------- The following report(s) may be obtained from: Jan Peterson Engineering Technology Applications Division Boeing Computer Services Company Mail Stop 9C-01 565 Andover Park West Tukwila, WA 98188 Submitted by: John Lewis --------------- %A R. Grimes %A H. Krakauer %A J. Lewis %A H. Simon %A S. Wei %T The solution of large dense generalized eigenproblems on the CRAY X-MP/24 with SSD %R ETA-TR-32 %D December 1985 %A J. Lewis %A H. Simon %T The impact of hardware gather/scatter on sparse Gaussian elimination %R ETA-TR-33 %D June 1986 %A R. Grimes %A J. Lewis %A H. Simon %T Eigenvalue problems and algorithms in structural engineering %R ETA-TR-35 %D march 1986 %A A. Erisman %A H. sSimon %T Education of engineers and scientists in supercomputing %R ETA-TR-37 %D July 1986 ##### BUFFALO ##### --------------- The following report(s) may be obtained from: P.J.Eberlein Computer Science Department Bell Hall SUNY/Buffalo Buffalo, NY, 14260 --------------- %A P. J. Eberlein %T Comments on some parallel Jacobi Orderings %R #86-16 %I Suny/Buffalo CS Dept., Bell Hall %C Buffalo, NY, 14260 %D August, 1986 %P 9 %X A one-sided Jacobi method for the hypercube is described, which utilizes the inherent parallelism of the Jacobi algorithm. A natural outcome of the implementation of the algorithm on a hypercube leads to some new Jacobi rotation sets for loops. Loops of even length for the hypercube architecture are described. %A P. J. Eberlein %T On One-Sided Jacobi Methods for Parallel Computation %R 86-17 %I Suny/Buffalo CS Dept., Bell Hall %C Buffalo, NY, 14260 %D August, 1986 %P 11 %X Convergence proofs are given for one-sided Jacobi/Hestenes methods for the singular value and eigenvalue problems. The limiting form of the matrix for the Hestenes method with optimization when the original matrix is normal is derived; this limiting matrix is block diagonal where the blocks are multiples of unitary matrices. A variation in the algorithm is shown to guarantee convergence to a diagonal matrix when the original matrix is symmetric. Implementation techniques for the hypercube are described. ##### CARNEGIE MELLON ##### --------------- The following report(s) may be obtained from: The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213 Taken from the UUCP network --------------- %A Patrick F. Muir %A Charles P. Neuman %T KINEMATIC MODELING OF WHEELED MOBILE ROBOTS" %R CMU-RI-TR-86-12 %I The Robotics Institute, Carnegie Mellon University %C Pittsburgh, PA 15213 %D June, 1986 %P 126 %X We formulate the "kinematic equations-of-motion" of wheeled mobile robots incorporating "conventional, omnidirectional," and "ball wheels." While our approach parallels the kinematic modeling of stationary manipulators, we extend the methodology to accommodate such special characteristics of wheeled mobile robots as "multiple closed-link chains, higher-pair contact points" between a wheel and a surface, and "unactuated" and "unsensed wheel degrees-of-freedom." We survey existing wheeled mobile robots to motivate our development. To communicate the kinematic features of wheeled mobile robots, we introduce a diagrammatic convention and nomenclature. We apply the "Sheth-Uicker" convention to assign coordinate axes and develop a "matrix coordinate transformation algebra" to derive the equations-of-motion. A "wheel Jacobian matrix" is formulated to relate the motions of each wheel to the motions of the robot. We combine the individual wheel equations to form the "composite robot equation-of-motion." We calculate the "sensed forward" and "actuated inverse" solutions and interpret the conditions which guarantee their existence. We interpret the properties of the composite robot equation to characterize the mobility of a wheeled mobile robot according to the "mobility characterization tree." Similarly, we apply "actuation" and "sensing characterization trees" to delineate the robot motions producible by the wheel actuators and discernable by the wheel sensors, respectively. We apply our kinematic model to "design, kinematics-based control, dead-reckoning" and "wheel slip detection." To illustrate the development, we formulate and interpret the kinematic equations-of-motion of six prototype wheeled mobile robots. ##### CHALMERS ##### --------------- The following report(s) may be obtained from: Axel Ruhe Department of Computer Science Chalmers University of Technology S-41296 Goteborg (telephone: int-46-31810100 ext. 1015) Submitted by: Axel Ruhe --------------- %A Owe Axelsson %A Gunhild Lindskog %T On the Eigenvalue Distribution of a Class of Preconditioning Methods %R Report 3 %I Department of Computer Science, Chalmers University of Technology %C S-41296 Goteborg, Sweden %D December 12, 1985 %X A class of preconditioning methods depending on a relaxation parameter is presented for the solution of large linear systems of equations Ax=b, where A is a symmetric positive definite matrix. The methods are based on an incomplete factorization of the matrix A and include both pointwise and blockwise factorizations. We study the dependence of the rate of convergence of the preconditioned conjugate gradient method on the distribution of eigenvalues of C\u-1\d A, where C is the preconditioning matrix. We also show graphic representations of the eigenvalues and present numerical tests of the methods. %A Thomas Ericsson %A Axel Ruhe %T Lanczos Algorithms and Field of Value Rotations for Symmetric Matrix Pencils %R Report 4 %I Department of Computer Science, Chalmers University of Technology %C S-41296 Goteborg, Sweden %D April 4, 1986 %X Iterative algorithms for the eigensolution of symmetric pencils of matrices are considered. It is shown that the symmetric Lanczos algorithm, the nonsymmetric Lanczos algorithm and the Arnoldi algorithm are closely related in this case. Applicability of this class of algorithms to indefinite pencils is discussed. A new field of values concept is used to describe the symmetric pencil problem. Then spectral transformation corresponds to a rotation in the complex plane, and the inertia count gives the number of eigenvalues corresponding to points in one of two half planes. %A Owe Axelsson %A Gunhild Lindskog %T On the Rate of Convergence of the Preconditioned Conjugate Gradient Method. %R Report 5 %I Department of Computer Science, Chalmers University of Technology %C S-41296 Goteborg, Sweden %D March 10, 1986 %X We derive new estimates for the rate of convergence of the conjugate gradient method by utilizing isolated eigenvalues of parts of the spectrum. We present a new generalized version of an incomplete factorization method and compare the derived estimates of the number of iterations with the number actually found for some elliptic difference equations and for a similar problem with a model empirical distribution function. ##### HARWELL ##### --------------- The following report(s) may be obtained from: Iain Duff CSS Div Harwell Laboratory Didcot, OXON OX11 0RA, England Contributed by: Iain Duff --------------- %A Iain S. Duff %T The influence of vector and parallel processors on numerical analysis %I CSS Div., Harwell Laboratory %C Didcot, OXON OX11 0RA, England %X It is now ten years since the first CRAY-1 was delivered to Los Alamos National Laboratory. Since then, supercomputers with vector processing capability have become widespread and important in the solution of problems in many areas of science and engineering involving large-scale computing. Their influence on numerical analysis has been less dramatic but we indicate the extent of that influence. In the last year or so, advanced @V0superminis@V1 that exhibit various more general forms of parallelism have been developed and marketed. We identify these and give some general principles which algorithm designers are using to take advantage of these parallel architectures. We argue that parallel processors are having a much stronger influence on numerical analysis than vector processors and illustrate our claims with examples from several areas of numerical analysis including linear algebra, optimization, and the solution of partial differential equations. %A Iain S. Duff %T Comments on the Solution of Sparse Linear Equations %R TM 58 %I Mathematics and Computer Science Division, %C Argonne National Laboratory, Argonne, Illinois 60439 %X We consider primarily direct methods for the solution of sparse linear equations. We first illustrate the wide range of sparse matrix types that arise in different application areas. It is clear that methods taking advantage of a particular structure should do better than a general technique designed for all classes of sparse matrices. We comment on this both philosophically and empirically. We discuss the techniques used in general solution schemes and those used in particular applications @mr for example, the solution of equations resulting from discretizations of partial differential equations. We also consider the use of direct methods as a preconditioning to iterative methods for solution. We look at work in combinatorial algorithms that relates to the solution of sparse equations and comment on some of the open problems in this and other areas. Throughout we comment on available software and the relative performance of the methods as implemented in those software packages. %A Ameet K. Dave %A Iain S. Duff %T Sparse matrix calculations on the CRAY-2 %I CSS Div., Harwell Laboratory %C Didcot, OXON OX11 0RA, England %X The CRAY-2 is sometimes viewed as a CRAY-1 with a faster cycle time. We show that this viewpoint is not completely appropriate by describing some of the important architectural differences between the machines and indicating how they can be used to facilitate numerical calculations. We have been testing kernels and codes on a CRAY-2 prior to the delivery of a machine to Harwell early next year and report some results on the solution of sparse equations which indicate that high efficiency can be obtained. We give details of one of the techniques for attaining this performance. We also comment on the use of parallelism in the solution of sparse linear equations on the CRAY-2. %A I. S. Duff %T The use of vector and parallel computers in the solution of large sparse linear equations %I CSS Div., Harwell Laboratory %C Didcot, OXON OX11 0RA, England %X We discuss three main approaches that are used in the direct solution of sparse unsymmetric linear equations and indicate how they perform on computers with vector or parallel architecture. The principal methods which we consider are general solution schemes, frontal methods, and multifrontal techniques. In each case, we illustrate the approach by reference to a package in the Harwell Subroutine Library. We consider the implementation of the various approaches on machines with vector architecture (like the CRAY-1) and on parallel architectures, both with shared memory and with local memory and message passing. %A Iain S. Duff %A Torbjorn Wiberg %T Implementations of {O(n SUP 1/2 tau )} assignment algorithms %I CSS Div., Harwell Laboratory %C Didcot, OXON OX11 0RA, England %X We examine a number of implementations and modifications of a 1973 algorithm of Hopcroft and Karp for permuting a sparse matrix so that there are no zeros on the diagonal. We describe our implementation of the original Hopcroft and Karp algorithm and compare this with modifications which we prove to have the same {O(n SUP 1/2 tau )} behaviour, where the matrix is of order {n} with { tau } entries. We compare the best of these with an efficient implementation of an algorithm whose worst case behaviour is {O(n tau )}. ##### ILLINOIS ##### --------------- The following report(s) may be obtained from: Rebecca J. Gering CSRD University of Illinois at Urbana-Champaign Urbana, Illinois 61801 Submitted by: Rebecca Gering --------------- %A Peiyi Tang %A Pen-Chung Yew %T Processor Self-Scheduling for Multiple-Nested Parallel Loops %R L00548 %I CSRD, University of Illinois at Urbana-Champaign %C Urbana, Illinois 61801 %D August 1986 %X Processor self-scheduling is a useful scheme in a multiprocessor system if the execution time of each iteration in a parallel loop is not known in advance and varies substantially, or if there are multiple nestings in parallel loops which makes static scheduling difficult and inefficient. By using efficient synchronization primitives, the operating system is not needed for loop scheduling. The overhead for the processor self- scheduling is small. We presented a processor self-scheduling scheme for a single-nested parallel loop, and extend the scheme to multi-nested parallel loops. Barrier synchronization mechanisms in the processors self-scheduling schemes are also discussed. %A David Kuck %A Edward Davidson %A Duncan Lawrie %A Ahmed Sameh %T Parallel Supercomputing Today and the Cedar Approach %R L00558 %I CSRD, University of Illinois at Urbana-Champaign %C Urbana, Illinois 61801 %D February 1986 %X More and more scientists and engineers are becoming interested in using supercomputers. Earlier barriers to using these machines are disappearing as software for their use improves. Meanwhile, new parallel supercomputer architectures are emerging that may provide rapid growth in performance. These systems may use a large number of processors with an intricate memory system that is both parallel and hierarchical; they will require even more advanced software. Compilers that restructure user programs to exploit the machine organization seem to be essential. A wide range of algorithms and applications is being developed in an effort to provide high parallel processing performance in many fields. The Cedar super- computer, presently operating with eight processors in parallel, uses advanced system and applications software developed at the University of Illinois during the past 12 years. This software should allow the number of processors in Cedar to be doubled annually, providing rapid performance advances in the next decade. %A Sy-Shin Lo %A Bernard Philippe %T The Symmetric Eigenvalue Problem on a Multiprocessor %R L00568 %I CSRD, University of Illinois at Urbana-Champaign %C Urbana, Illinois 61801 %D April 1986 %X This paper is a survey of optimal methods for solving the symmetric eigenvalue problem on a multiprocessor. Although the inherent parallelism of the Jacobi method is well known, the convergence is not insured and the total number of operations is larger than that of the methods which transform the full matrix into a tridiagonal matrix. In this paper we are concerned with the methods which deal with the tridiagonalized eigenvalue systems. In Section 2 we review the sequential methods for solving symmetric eigenvalue problems by tridiagonal reduction using the appropriate routines from EISPACK. Section 3 discusses the different ways of exploiting parallelism, examples of linear recurrence and orthogonali- zation are presented. Section 4 and Section 5 deal with the two algorithms, SESUPD, a parallel version of TQL2 in EISPACK, and TREPS, a parallel version of BISECT+TINVIT, respectively. In Section 6 we compare these two approaches. %A Gene Golub %A Robert Plemmons %A Ahmed Sameh %T Parallel Block Schemes for Large Scale Least Squares Computations %R L00574 %I CSRD, University of Illinois at Urbana-Champaign %C Urbana, Illinois 61801 %D April 1986 %X Large scale least squares computations arise in a variety of scientific and engineering problems, including geodetic adjustments and surveys, medical image analysis, molecular structures, partial differential equations and substructuring methods in structural engineering. In each of these problems, matrices often arise which possess a block structure which reflects the local connection nature of the underlying physical problem. For example, such super-large nonlinear least squares computations arise in geodesy. Here the coordinates of positions are calculated by interatively solving overdetermined systems of nonlinear equations by the Gauss-Newton method. The U.S. National Geodetic Survey will complete this year (1986) the readjustment of the North American Datum, a problem which involves over 540 thousand unknowns and over 6.5 million observations (equations). The observation matrix for these least squares computations has a block angular form with 161 diagonal blocks, each containing 3 to 4 thousand unknowns. In this paper parallel schemes are suggested for the orthogonal factorization of matrices in block angular form and for the associated backsubstitution phase of the least squares computations. In addition, a parallel scheme for the calculation of certain elements of the covariance matrix for such problems is described. It is shown that these algorithms are ideally suited for multiprocessors with three levels of parallelism such as the Cedar system at the University of Illinois. %A Edward Davidson %A David Kuck %A Duncan Lawrie %A Ahmed Sameh %T Supercomputing Tradeoffs and the Cedar System %R L00577 %I CSRD, University of Illinois at Urbana-Champaign %C Urbana, Illinois 61801 %D May 1986 %X A number of tradeoffs made in supercomputer and minisupercomputer designs are discussed. The Cedar System is discussed in this context. Applications and software work on the Cedar System are presented. %A N. R. Nandakumar %T Polynomial Preconditioning of Symmetric Indefinite Systems %R L00580 %I CSRD, University of Illinois at Urbana-Champaign %C Urbana, Illinois 61801 %D June 1986 %X In this paper a new algorithm is proposed to solve indefinite symmetric sparse linear systems using polynomial preconditioning. The precondi- tioning polynomials are derived using simple calculus techniques. In practice this algorithm, unlike other algorithms proposed in the literature, does not require complete knowledge of the intervals containing the spectrum of the given matrix. This method is superior to CG on normal equations, SYMMLQ and Saad's GCI algorithm. Also the algorithm is amenable for implementing on parallel machines. The performance of the algorithm is compared with Saad's GCI algorithm on the minisupercomputer Alliant FX/8. ##### MARYLAND ##### --------------- The following report(s) may be obtained from: Howard C. Elman University of Maryland Computer Science Technical Report 1704 Submitted by: Howard Elman --------------- %A Howard C. Elman %T Approximate Schur Complement Preconditioners for Serial and Parallel Computers %R Technical Report 1704 %I University of Maryland, Computer Science %X We consider a class of preconditioning techniques for sparse matrices based on computing the Schur complement of a (suitably ordered) matrix. The techniques generalize the reduced system methodology for 2-cyclic matrices to non-2-cyclic matrices, and in addition, they are well-suited to parallel architectures. We demonstrate their effectiveness with numerical experiments on a nine-point finite difference operator, and we present an analysis showing that they can be implemented efficiently on multiprocessors. ##### MINNESOTA ##### --------------- The following report(s) may be obtained from: Max Benson Assistant Professor of Computer Science University of Minnesota-Duluth Taken from the UUCP network --------------- %A Max Benson %T ENVIRONMENTS: An Algebraic Computing Technique %R 86-10 %I University of Minnesota-Duluth %C Duluth, Minnesota %D July, 1986 %X An environment is a representation of an algebraic structure within a program by a data structure and associated primitives. This paper describes a programming technique and its implementation in the C language based on environments. The programmer can encode algorithms in algebra by setting up the environment and then making high level calls on primitives for natural algebraic operations. An example of working program written using this technique is given which computes the Todd polynomials. ##### NYU ##### --------------- The following report(s) may be obtained from: Michael J. Passaro Administrative Manager New York University Ultracomputer Research Laboratory Courant Institute 251 Mercer St., New York, NY 10012 Taken from the UUCP network. --------------- %A Dennis Shasha %A Marc Snir %T Efficient and Correct Execution of Parallel Programs That Share Memory %R Ultracomputer Note #96 %I Ultracomputer Research Laboratory %C Courant Institute, NYU, %D March, 1986 %A Anne Greenbaum %T Solving Sparse Triangular Linear Systems Using FORTRAN with Parallel Extensions on the NYU Ultracomputer Prototype %R Ultracomputer Note #99 %I Ultracomputer Research Laboratory %C Courant Institute, NYU, %D April, 1986 --------------- The following report(s) may be obtained from: James W. Demmel Courant Institute New York, NY 10012 Submitted by: James Demmel --------------- %T Accurate Solutions of Ill-posed Problems in Control Theory %A James W. Demmel %A Bo Kagstrom %I Courant Institute, New York University %C New York, NY 10012 %X We present computable, guaranteed error bounds for controllable subspaces and uncontrollable modes, unobservable subspaces and unobservable modes, supremal (A,C) invariant subspaces in ker D, supremal (A,C) controllability subspaces in ker D, the uncontrollable modes within the supremal (A,C) invariant subspace in ker D, and invariant zeroes. In particular our bounds apply in the nongeneric case when the solutions are ill-posed. We do this by showing that all these features are eigenspaces and eigenvalues of certain singular matrix pencils, which means they may all be computed by a single algorithm to which we can apply a perturbation theory for general singular matrix pencils. Numerical examples are included. --------------- The following report(s) may be obtained from: Dick Dee Courant Institute 251 Mercer Street New York, NY 10012 or Submitted by: Dick Dee --------------- %A Stephen E. Cohn %A Dick P. Dee %I Courant Institute, New York University %C 251 Mercer Street, New York, NY 10012 %X The situation in which one would like to solve a numerical initial value problem for a set of partial differential equations (PDE), but cannot for lack of complete initial data, is arising ever more frequently in applied sciences and engineering. The attempt to estimate the evolving state by inserting incomplete data into a numerical model as they become available at different instants of time is called "data assimilation" or "filtering." We show that if data generated by linear PDE are inserted properly, then complete observability of the discrete numerical model is necessary and sufficient for asymptotic stability of the data assimilation process. This complete observability means that, had the data been generated instead by the discrete model, then they would define the state of the model uniquely after some finite time. Simple observability criteria for discretizations of linear, constant- coefficient PDE on periodic domains are formulated in terms of properties of the symbol of the numerical scheme. It is shown that spurious numerical dispersion can detract from observability by yielding a multi-valued symbol. While observability for the advection equation demands the addition of dissipation to the leapfrog and Crank-Nicolson schemes, dissipation is not needed for second-order and sixth-order accurate box schemes. ##### OAK RIDGE ##### --------------- The following report(s) may be obtained from: D. C. Human Mathematical Sciences P. O. Box Y, Bldg. 9207A Oak Ridge National Laboratory Oak Ridge, Tennessee 37831 Submitted by S. Thompson, A. D. Solomon --------------- %A S. Thompson %T Remarks on the Choice of a Stiff Ordinary Differential Equation Solver %R ORNL-6189 %I Oak Ridge National Laboratory %C Oak Ridge, Tennessee %D March, 1986 %X This report discusses several aspects of the solution of fluid flow problems. A model problem is described which captures several of the salient characteristics of such problems. The model problem is derived from the one-dimensional Euler equations. It corresponds to the subcooled liquid region of a three region reactor steam generator model. The defining partial differential equations are discretized spatially using the method of pseudo-characteristics. The resulting system of ordinary differential equations is then solved by the method of lines using each of several available ordinary differential equation (ode) solvers. In addition to demonstrating that fluid flow problems can be solved effectively using adaptive mathematical software, the results also illustrate the typical performance of each solver as well as the relative merits of special solver features (e.g., automatic method switching and exploitation of problem sparsity or bandedness). The model problem is also modified and used to illustrate several commonly observed characteristics of fluid flow models. The results illustrate the potential effect on solver performance of characteristics such as inaccurate water property calculations. Consequently, they explain apparent anomalies often attributed incorrectly to poor solver design and algorithmic implementation. The results also support the choice of the sparse ordinary differential solver LSODES for the solution of fluid flow problems. %A A. D. Solomon %A D. G. Wilson %A V. Alexiades %T An Approximate Analysis of the Formation of a Buoyant Solid Sphere in a Supercooled Melt %R ORNL-6212 %I Oak Ridge National Laboratory %C Oak Ridge, Tennessee %D March 1986 %X A mathematical model is presented for the idealized formation and development of a bouyant sphere solidifying in an infinite pool of supercooled liquid. The solid and liquid are of the same pure material and the solid is less dense than the liquid. Initially the liquid is at a uniform temperature that is below its equilibrium freezing temperature, @T sub cr@, but above the so called hypercooled temperature, @T sub cr@ - @H/c sub L ^@. Here @H@ and @c sub L@ are the latent heat of solidification and the specific heat of the liquid respectively. An approximate solution is derived based on the Megerlin approximation method. %A V. Alexiades %A A. D. Solomon %T Critical Radius for Nucleation %R ORNL/TM-9931 %I Oak Ridge National Laboratory %C Oak Ridge, Tennessee %D April 1986 %X The free energy of formation and the critical radius for homogeneous nucleation of a spherical nucleus in supercooled liquid, at given temperature and ambient pressure, are determined, taking fully into account surface tension, curvature, and pressure effects. We allow the specific heats and densities of the two phases to be different and all thermophysical properties to be temperature dependent. In the simple case in which classical nucleation theory is valid, our result predicts a critical radius of about 80% of the classical value. %A V. Alexiades %A A. D. Solomon %A D. G. Wilson %T The Formation of a Solid Nucleus in Supercooled Liquid %R ORNL-6280 %I Oak Ridge National Laboratory %C Oak Ridge, Tennessee %D June 1986 %X A careful analysis of the thermodynamics of a phase transition involving supercooled liquid is presented. Relations are developed for equilibrium temperature, pressures and volumes of solid and liquid from conservation relations and mathematical statements of thermal, mechanical and chemical equilibrium. Surface area, curvature and pressure effects are considered. Initial data are the temperature, pressure and volume of a supercooled liquid in which nucleation is assumed to have occurred. Generalized Clapeyron type equations in the presence of curved interfaces and a generalization of the Gibbs-Thompson relation between curvature of the phase change interface and the transition temperature at the interface are derived and discussed. %A A. D. Solomon %A D. G. Wilson %T A Stefan-Type Problem With Void Formation and its Explicit Solution %R ORNL-6277 %I Oak Ridge National Laboratory %C Oak Ridge, Tennessee %D June 1986 %X The density of most materials changes under melting and freezing. For certain materials being considered as potential latent heat storage materials for use in a space station, this density change may be large. A density change induces a change of volume of the material occupying a given container and this creates vapor "bubbles" or "voids." We have formulated a problem that models a phase change process with such a void and that has an explicit solution. We examine the solution to gain a further understanding of the thermal and phase change performance of a material in which such voids form. We also look at the related problem of melting a material in which a void is initially present. Examples are given of the performance of a lithium fluoride phase change material subject to melting and freezing. %A A. D. Solomon %A V. Alexiades %A D. G. Wilson %A G. A. Geist %A J. Kerper %T An Enthalpy Method for the Solidification of a Supercooled Liquid %R ORNL-6217 %I Oak Ridge National Laboratory %C Oak Ridge, Tennessee %D March 1986 %X The classical enthalpy formulation of phase change processes does not permit modeling solidification of supercooled liquids. This report describes an enthalpy-based method for simulating a freezing process involving a planar front moving into a supercooled but not hypercooled liquid. The method is applicable when the liquid is initially below its equilibrium freezing temperature, @T sub cr@, but above @T sub cr~-~H@/@c sub L~@. Here @H@ and @c sub L@ are the latent heat of solidification and the specific heat of the liquid respectively. The report also discusses a computer implementation of the method in one-dimension and results of its application to a particular problem with an explicit solution. %A A. D. Solomon %A V. Alexiades %A D. G. Wilson %A J. Greenberg %T A Hyperbolic Stefan Problem with Discontinuous Temperature %R ORNL-6216 %I Oak Ridge National Laboratory %C Oak Ridge, Tennessee %D March 1986 %X In an earlier paper a Stefan problem for hyperbolic heat transfer was formulated under the condition of continuity of the temperature at the moving front. In this paper we examine this assumption and present an alternative model in which continuity is not imposed. For this case, a problem with an explicit solution is presented, as are some qualitative properties of solutions to some similar problems. In addition, we derive quasi-steady approximate solutions to certain other benchmark problems. ##### PENN ##### --------------- The following report(s) may be obtained from: Computer Science Department Whitmore Lab Pennsylvania State University University Park, PA, 16802, U.S.A. Submitted by: Alex Pothen --------------- %A Alex Pothen %T Equilibrium graphs in structural optimization %R CS-86-22 %I Computer Science Department, Penn State UNiv. %C Whitmore Lab, Pennsylvania State University, University Park, PA, 16802 %D August, 1986 %X We introduce the equilibrium graph, the bipartite graph of the equilibrium matrix, as a useful tool in the computation of a sparse self-stress matrix. This matrix is a basis for the null space of the equilibrium matrix, and is needed in the force method of structural optimization. We argue that this graph conveys more information about the physical structure than the equilibrium matrix. The concept of this graph helps in the design of an equilibrium graph algorithm to compute a self-stress matrix. The algorithm has two phases: in the first graph phase, a sizable number of the columns of the self-stress matrix is computed from the equilibrium graph. In a second triangular phase, the triangular algorithm (Coleman and Pothen (1986)) is used to compute the rest of the columns. For two of the problems, this algorithm computes sparsest self-stress matrices. For others, it speeds up the computations considerably. ##### PURDUE ##### --------------- The following report(s) may be obtained from: Manolis Vavalis Computer Science Department Purdue University Submitted by: Manolis Vavalis --------------- %A E. N. Houstis %A E. A. Vavalis %A J. R. Rice %T Convergence of O( h sup 4 ) Cubic Spline Collocation Methods for Elliptic Partial Differential Equations %I Computer Science Dept., Purdue University. %D May 15, 1986. %P 33 %X This paper present a new class of collocation methods using cubic splines for solving elliptic partial differential equations (PDEs). The error bounds obtained for these methods are optimal. The methods are formulated and a convergence analysis is carried out for a board class of elliptic PDEs. Experimental results confirm the optimal convergence and indicate that these methods are computationally more efficient than methods based on either collocation with Hermite cubics or on Galerkin with cubic splines. Various iterative methods have been used to solve the cubic spline collocation equations. ##### WASHINGTON ##### --------------- The following report(s) may be obtained from: Technical Reports Computer Science Department Washington State University Pullman, WA 99164-1210 U.S.A. Taken from the UUCP network. --------------- %A Dilip Sarkar %T LESSA: AN ARRAY TO SOLVE A SET OF LINEAR EQUATIONS %R CS-86-154 Computer Science Department %I Washington State University %C Pullman, WA 99164-1210 %X A dedicated linear array of simple processors is proposed to solve a set of linear equations. Data structure and algorithm also presented for the array to solve a set of @n@ linear equations in @O(n sup 2+3.n )@ time on an array of @n@ processors. The given algorithm is a parallelization of the Gaussian elimination algorithm. The data input to the array is purely sequential. The algorithm is optimal, within a constant, in its time and area requirements. %A Alan Genz %T THE NUMERICAL EVALUATION OF MULTIPLE INTEGRALS ON PARALLEL COMPUTERS %R CS-86-161 Computer Science Department %I Washington State University %C Pullman, WA 99164-1210 %X The problem of efficient implementation of numerical integration algorithms on parallel computers is considered. First, a general discussion of both adaptive and nonadaptive algorithms, including possible differences in implementation for vector machines, SIMD machines and MIMD machines is given. The implementation of a globally adaptive algorithm on three different parallel computers is discussed, and test results are reported. ##### WATERLOO ##### --------------- The following report(s) may be obtained from: Andy Conn Computer Science Department University of Waterloo Waterloo, Ontario N2L 3G1 Submitted by: Andy Conn. --------------- %A A.R. Conn %A N.I.M. Gould %A Ph.L. Toint %T Global convergence of a class of trust region algorithms for optimization with simple bounds. %R CS-86-31 %I Computer Science Department, University of Waterloo %C Waterloo, Ontario, CANADA N2L 3G1 %X This paper extends the known excellent global convergence properties of trust region algorithms for unconstrained optimization to the case where bounds on the variables are present. Weak conditions on the size of the Hessian approximations are considered. It is also shown that the proposed algorithms reduce to an unconstrained calculation after finitely many iterations, allowing a fast asymptotic rate of convergence. %A A.R. Conn %A N.I.M. Gould %A Ph.L. Toint %T Testing a class of methods for solving minimization problems with simple bounds on the variables. %R CS-86-45 %I Computer Science Department, University of Waterloo %C Waterloo, Ontario, CANADA N2L 3G1 %X We describe the results of a series of tests upon a class of new methods of trust region type for solving the simple bound constrained minimization problem. The results are encouraging and lead us to believe that the methods will prove useful in solving large problems. --------------- The following report(s) may be obtained from: Henry Wolkowicz Department of Combinatorics and Optimization University of Waterloo Waterloo, Ontario N2L 3G1 Submitted by: Henry Wolkowicz --------------- %T A Volume and Constraint Reducing Algorithm for Linear Programming %A Henry Wolkowicz %A Adi Ben-Israel %X An algorithm is presented for solving the linear programming problem. At each iteration, the algorithm moves through the middle of the feasible set to a nonadjacent vertex. It simultaneously discards 'half' of the feasible set and at least one constraint is made redundant. The algorithm is unaffected by degeneracy. ##### WEIDLINGER ##### --------------- The following report(s) may be obtained from: Victor Pereyra Weidlinger Associates 620 Hansen Way Palo Alto, CA 94304 Submitted by: Victor Pereyra --------------- %A V. Pereyra %A G. Wojcik %T Numerical Methods for Inverse Problems in Three-Dimensional Geophysical Modeling %I Weidlinger Associates %C 620 Hansen Way, Palo Alto, CA 94304 %P 70 %D July 31, 1986 ##### WISCONSIN ##### --------------- The following report(s) may be obtained from: Technical Reports Librarian Computer Science Department University of Wisconsin 1210 W. Dayton St. Madison, WI 53706 (Note that many reports are not free of charge. Make checks payable to the University of Wisconsin. Purchase orders cannot be accepted.) Taken from the UUCP network. --------------- %A Raphael Finkel %A A. P. Anantharaman %A Sandip Dasgupta %A Tarak S. Goradia %A Prasanna Kaikini %A Chun-Pui Ng %A Murali Subbarao %A G. A. Venkatesh %A Sudhanshu Verma %A Kumar A. Vora %T Experience With Crystal, Charlotte and Lynx %D February 1986 %R TR 630 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %O $1.44 %X Abstract: This paper describes the most recent implementations of distributed algorithms at Wisconsin that use the Crystal multicomputer, the Charlotte operating system, and the Lynx language. This environment is an experimental testbed for design of such algorithms. Our report is meant to show the range of applications that we have found reasonable in such an environment and to give some of the flavor of the algorithms that have been developed. We do not claim that the algorithms are the best possible for these problems, although they have been designed with some care. In several cases they are completely new or represent significant modifications of existing algorithms. We present distributed implementations of B trees, systolic arrays, prolog tree search, the travelling salesman problem, incremental spanning trees, nearest-neighbor search in k-d trees, and the Waltz constraint-propagation algorithm. Our conclusion is that the environment, although only recently available, is already a valuable resource and will continue to grow in importance in developing new algorithms. %A O. L. Mangasarian %A R. De Leone %T Error Bounds for Strongly Convex Programs and (Super)Linearly Convergent Iterative Schemes for the Least 2-Norm Solution of Linear Programs %D February 1986 %R TR 631 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %O $0.00 %X Abstract: Given an arbitrary point (x,u) in &R sup n& x &R sup m&+, we give bounds on the Euclidean distance between x and the unique solution x to a strongly convex program in terms of the violations of the Karush-Kuhn- Tucker conditions by the arbitrary point (x,u). These bounds are then used to derive linearly and superlinearly convergent iterative schemes for obtaining the unique least 2-norm solution of a linear program. These schemes can be used effectively in conjunction with the successive overrelaxation (SOR) methods for solving very large sparse linear programs. %A Klaus Hollig %T Box Splines %D April 1986 %R TR 640 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %O $0.00 %X Abstract: This report gives an introduction to multivariate cardinal spline theory. It is based on joint work with Carl de Boor and Sherman Riemenschneider and the particular topics discussed are: recurrence relations for box splines, approximation order, interpolation, convergence to functions of exponential type and subdivision algorithms. %A Michael D. Chang %A Michael Engquist %A Raphael Finkel %A Robert Meyer %T A Parallel Algorithm for Generalized Networks %D June 1986 %R TR 642 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %O $0.00 %X Abstract: A parallel algorithm for the solution of linear generalized network optimization problems is presented. This method decomposes the original network into initial collections of quasi-trees that are distributed among a set of processors that optimize in parallel their corresponding "local" problems. Periodically, the processors exchange information on their local problems, and one or more quasi-trees may be moved between processors as desirable links between quasi-trees on different processors are determined or for load balancing purposes. This procedure has been implemented on the CRYSTAL multicomputer, and computational results have been obtained on problems with up to 28,000 variables. For problems whose optimal solutions contain numerous quasi-trees, the efficiency of this parallel implementation is about 50%. %A Charles V. Stewart %A Charles R. Dyer %T Convolution Algorithms on the Pipelined Image-Processing Engine %D May 1986 %R TR 643 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %O $0.00 %X Abstract: In this paper we present two algorithms for computing an N by N convolution on the Pipelined Image-Processing Engine (PIPE). PIPE is a special-purpose machine for low-level vision consisting of eight processing stages connected in a pipelined fashion. Each stage can compute a number of different basic image functions. Each of the algorithms decomposes the solution into a sequence of 3 by 3 neighborhood operations, shifts and additions. The first algorithm divides the results of the 3 by 3 partial convolutions into groups of concentric rings of images and successively collapses the images on the outer ring onto the next ring, merging the results until a single result image is computed. The second algorithm divides the partial convolution images into eight sectors and computes each sector independently. For a 27 by 27 convolution of a 256 by 256 image the first algorithm requires 0.633 seconds, while the second requires 0.683 seconds. These algorithms for PIPE are also shown to compare favorably with algorithms for arbitrary sized kernels on fast general purpose hardware, the MPP and Warp. %A Klaus Hollig %T Geometric Continuity of Spline Curves and Surfaces %D June 1986 %R TR 645 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %O $0.00 %X Abstract: We review &beta&-spline theory for curves and show how some of the concepts can be extended to surfaces. Our approach is based on the Bezier form for piecewise polynomials which yields simple geometric characterizations of smoothness constraints and shape parameters. For curves most of the standard "spline calculus" has been developed. We discuss in particular the construction of B-splines, the conversion for B-spline to Bezier representation and interpolation algorithms. A comparable theory for spline surfaces for general meshes does at present not exist. We merely describe how to join triangular and rectangular patches and discuss the corresponding &beta&-spline constraints in terms of the Bezier representation. %A O. L. Mangasarian %A R. De Leone %T Parallel Successive Overrelaxation Methods for Symmetric Linear Complementarity Problems and Linear Programs %D June 1986 %R TR 647 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %O $0.00 %X Abstract: A parallel successive overrelaxation (SO) method is proposed for the solution of the fundamental symmetric linear complementarity problem. Convergence is established under a relaxation factor which approaches the classical value of 2 for a loosely coupled problem. The parallel SOR approach is then applied to solve the symmetric linear complementarity problem associated with the least norm solution of a linear program. .