waashk/acm huggingface dataset:
band reduction algorithms revisited  in this paper we explain some of the changes that have been incorporated in the latest version of the lapack subroutine for reducing a symmetric banded matrix to tridiagonal form. these modifications improve the performance for larger-bandwidth problems and reduce the number of operations when accumulating the transformations onto the identity matrix, by taking advantage of the structure of the initial matrix. we show that similar modifications can be made to the lapack subroutines for reducing a symmetric positive definite generalized eigenvalue problem to a standard symmetric banded eigenvalue problem and for reducing a general banded matrix to bidiagonal form to facilitate the computation of the singular values of the matrix.  linda kaufman
numerical methods for infinite markov processes  the estimation of steady state probability distributions of discrete markov processes with infinite state spaces by numerical methods is investigated. the aim is to find a method applicable to a wide class of problems with a minimum of prior analysis. a general method of numbering discrete states in infinite domains is developed and used to map the discrete state spaces of markov processes into the positive integers, for the purpose of applying standard numerical techniques. a method based on a little used theoretical result is proposed and is compared with two other algorithms previously used for finite state space markov processes.  p. j.b. king i. mitrani
exact real computer arithmetic with continued fractions  we introduce a representation of the computable real numbers by continued fractions. this deals with the subtle points of undecidable comparison an integer division, as well as representing the infinite 1/0 and undefined 0/0 numbers. two general algorithms for performing arithmetic operations are introduced. the algebraic algorithm, which computes sums and products of continued fractions as a special case, basically operates in a positional manner, producing one term of output for each term of input. the transcendental algorithm uses a general formula of gauss to compute the continued fractions of exponentials, logarithms, trigonometric functions, as well as a wide class of special functions. a prototype system has been implemented in lelisp, and the performance of these algorithms is promising.  jean vuillemin
algorithm 799: revolve: an implementation of checkpointing for the reverse or adjoint mode of computational differentiation  in its basic form, the reverse mode of computational differentiation yields the gradient of a scalar- valued function at a cost that is a small multiple of the computational work needed to evaluate the function itself. however, the corresponding memory requirement is proportional to the run-time of the evaluation program. therefore, the practical applicability of the reverse mode in its original formulation is limited despite the availability of ever larger memory systems. this observation leads to the development of checkpointing schedules to reduce the storage requirements. this article presents the function revolve, which generates checkpointing schedules that are provably optimal with regard to a primary and a secondary criterion. this routine is intended to be used as an explicit "controller" for running a time-dependent applications program.  andreas griewank andrea walther
on the significance of the theory of convex polyhedra for formal algebra this paper was originally published as ber die bedeutung der theorie der konvexen polyeder f r die formale algebra in jahresbericht d. deutschen math. ver. **_30_** (1922): 98-99. it is based on a talk given in jena to the german mathematical society on 23 september 1921. quoted in ostrowski's later paper on multiplication and factorization of polynomials. i lexicographic orderings and extreme aggregates of terms. aequationes math. **_13_** (1975): 201-228. a. ostrowski
static analysis of large programs (invited talk) (abstract only): some experiences  our research group at microsoft has spent some effort over the last few years attempting to apply static analysis methods to large application programs (over a million lines of code). in the first part of the talk, i will share some of the insights we have gained along the way. the first insight is that the static analysis method of interest must scale to large programs. it must scale in terms of performance, both running time and memory requirements. the interesting complexity metric is average-case behaviour. the analysis must also scale in terms of the quality of information produced. this metric is hard to measure, and depends on the problem to be solved. the second insight is that large commercial applications differ from the benchmark programs typically used in the literature in many ways beyond sheer size: for instance, they routinely circumvent the type system, they make use of every conceivable language feature, they use large shared libraries, they contain some very large automatically generated functions, they define functions with large numbers of call sites, and they include many indirect call sites. all of these characteristics make analysis hard. in particular, they make the implementation of a scalable analysis an exercise in careful engineering.  in the second part of the talk, i will make the claim that it is possible to develop scalable static analysis methods for large programs, using the following approach: first, implement an efficient algorithm, and carefully engineer it to scale. important requirements are modularity, a complete parser, and some form of garbage collection. next, identify the conceptual limitations of the efficient algorithm, and examine the test programs to identify common cases or idioms in the code that expose these limitations. finally, extend the original algorithm in a principled manner to account for these common cases, without compromising performance. i will use my work on pointer analysis of large programs as an example of this approach. the key insight is that it is possible to identify common idioms in the code that are the bottlenecks for efficient algorithms. a scalable static analysis method can be developed if these idioms can be identified and accommodated.  manuvir das
exploiting zeros on the diagonal in the direct solution of indefinite sparse symmetric linear systems  we describe the design of a new code for the solution of sparse indefinite symmetric linear systems of equations. the principal difference between this new code and earlier work lies in the exploitation of the additional sparsity available when the matrix has a significant number of zero diagonal entries. other new features have been included to enhance the execution speed, particularly on vector and parallel machines.  i. s. duff j. k. reid
software considerations for the "black box" solver fidisol for partial differential equations  fidisol is a program package for the solution of nonlinear systems of two- dimensional and three-dimensional elliptic and parabolic partial differential equations (pdes) with nonlinear boundary conditions (bcs) on the boundaries of a rectangular domain. a finite difference method (fdm) with an arbitrary grid and arbitrary consistency order is used, these are either prescribed by the user or are self-adapted for a given relative tolerance. fidisol has been designed to be fully vectorizable on vector computers. in this paper we discuss several problems from the viewpoint of software development and user interface, for example, how to deliver the pdes and bcs to fidisol and how to allow a flexible use by a suitable parameter list.  willi schönauer eric schnepf
a fast parallel algorithm for the maximal independent set problem  a parallel algorithm is presented that accepts as input a graph g and produces a maximal independent set of vertices in g. on a p-ram without the concurrent write or concurrent read features, the algorithm executes in o((log n)4) time and uses o((n/(log n))3) processors, where n is the number of vertices in g. the algorithm has several novel features that may find other applications. these include the use of balanced incomplete block designs to replace random sampling by deterministic sampling, and the use of a "dynamic pigeonhole principle" that generalizes the conventional pigeonhole principle.  richard m. karp avi wigderson
algorithm 658: a program for solving separable elliptic equations  this paper persents a program serrg2 that solves separable elliptic equations on a rectangle. the program uses a matrix decomposition technique to directly solve the linear system arising from a rayleigh-ritz-galerkin approach with tensor product b-splines to solve the separable partial differential equation. this approach permits high-order discretizations, variable meshes, and multiple knots.  linda kaufman daniel d. warner
algorithm 678 btpec: sampling from the binomial distribution  the fortran implementation of an exact, uniformly fast algorithm for generating the binomial, random variables is presented. the algorithm is numerically stable and is faster than other published algorithms. the code uses only standard fortran statements and is portable to most computers; it has been tested on the ibm 370, 3033, 4381, dec vax 11/780, sun 3/50, cdc 6500-6600, encore multimax, and apple mcintosh plus. a driver program is also included.  voratas kachitvichyanukul bruce w. schmeiser
sprint2d: adaptive software for pdes  sprint2d is a set of software tools for solving both steady an unsteady partial differential equations in two-space variables. the software consists of a set of coupled modules for mesh generation, spatial discretization, time integration, nonlinear equations, linear algebra, spatial adaptivity, and visualization. the software uses unstructured triangular meshes and adaptive local error control in both space and time. the class of problems solved includes systems of parabolic, elliptic, and hyperbolic equations; for the latter by use of riemann-solver- based methods. this article describes the software and shows how the adaptive techniques may be used to increase the reliability of the solution for a burgers' equations problem, an electrostatics problem from elastohydrodynamic lubrication, and a challenging gas jet problem.  m. berzins r. fairlie s. v. pennington j. m. ware l. e. scales
numerical comparisons of some explicit runge-kutta pairs of orders 4 through 8  we performed numerical testing of six explicit runge-kutta pairsranging in order from a (3,4) pair to a (7,8) pair. all the testproblems had smooth solutions and we assumed dense output was notrequired. the pairs were implemented in a uniform way. in particular,the stepsize selection for all pairs was based on the locally optimalformula. we tested the efficiency of the pairs, to what extent toleranceproportionality held, the accuracy of the local error estimate andstepsize prediction, and the performance on mildly stiff problems. wealso showed, for these pairs, how the performance could be alterednoticeably by making simple changes to the stepsize selection strategy.as part of the work, we demonstrated new ways of presenting numericalcomparisons.  \\---from the author's abstract p. w. sharp
multiplicative, congruential random-number generators with multiplier ± 2_k_1 ± 2_k_2 and modulus 2_p_ \\- 1  the demand for random numbers in scientific applications is increasing. however, the most widely used multiplicative, congruential random-number generators with modulus 231 1 have a cycle length of about 2.1 × 109. moreover, developing portable and efficient generators with a larger modulus such as 261 1 is more difficult than those with modulus 231 1\\. this article presents the development of multiplicative, congruential generators with modulus m = 2p 1 and four forms of multipliers: 2k1 − 2k2, 2k1 \\+ 2k2, m 2k1 \\+ 2k2, and m 2k1 2k2, k1 > k2\\. the multipliers for modulus 231 1 and 261 1 are measured by spectral tests, and the best ones are presented. the generators with these multipliers are portable and vary fast. they have also passed several empirical tests, including the frequency test, the run test, and the maximum-of-t test.  pei-chi wu
control-theoretic techniques for stepsize selection in implicit runge-kutta methods  the problem of stepsize selection in implicit runge-kutta schemes is analyzed from a feedback control point of view. this approach leads to a better understanding of the relation between stepsize and error. a new dynamical model describing this relation is derived. the model is used as a basis for a new stepsize selection rule. this rule achieves better error control at little extra expense. the properties of the new model and the improved performance of the new error control are demonstrated using both analysis and numerical examples.  kjell gustafsson
more efficient computation of the complex error function  gautschi has developed an algorithm that calculates the value of the faddeeva function w(z) for a given complex number z in the first quadrant, up to 10 significant digits. we show that by modifying the tuning of the algorithm and testing the relative rather than the absolute error we can improve the accuracy of this algorithm to 14 significant digits throughout almost the whole of the complex plane, as well as increase its speed significantly in most of the complex plane. the efficiency of the calculation is further enhanced by using a different approximation in the neighborhood of the origin, where the gautschi algorithm becomes ineffective. finally, we develop a criterion to test the reliability of the algorithm's results near the zeros of the function, which occur in the third and fourth quadrants.  g. p. m. poppe c. m. j. wijers
an algorithm for finding hamilton cycles in random graphs  this paper describes a polynomial time algorithm ham that searches for hamilton cycles in undirected graphs. on a random graph its asymptotic probability of success is that of the existence of such a cycle. if all graphs with n vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected time. finally, it is used in an algorithm for solving the symmetric bottleneck travelling salesman problem with probability tending to 1, as n tends to ∞.  b bollobás t i fenner a m frieze
on the discrepancy of gfsr pseudorandom numbers  a new summation formula based on the orthogonal property of walsh functions is devised. using this formula, the k-dimensional discrepancy of the generalized feedback shift register (gfsr) pseudorandom numbers is derived. the relation between the discrepancy and k-distribution of gfsr sequences is also obtained. finally the definition of optimal gpsr pseudorandom number generators is introduced.  shu tezuka
algorithm 732; solvers for self-adjoint elliptic problems in irregular two- dimensional domains  software is provided for the rapid solution of certain types of elliptic equations in rectangular and irregular domains. specifically, solutions are found in two dimensions for the nonseparable self- adjoint elliptic problem  g y =f , where g and f are given functions of x and y, in two- dimensional polygonal domains with dirichlet boundary conditions. helmholtz and poisson problems in polygonal domains and the general variable coefficient problem i.e.,g 1 in a rectangular domain may be treated as special cases. the method of solution combines the use of the capacitance matrix method, to treat the irregular boundary, with an efficient iterative method (using the laplacian as preconditioner) to deal 2 with nonseparability. each iterative step thus involves solving the poisson equation in a rectangular domain. the package includes separate, easy-to-use routines for the helmholtz problem and the general problem in rectangular and general polygonal domains, and example driver routines for each. both single- and double-precision routines are provided.  second-order-accurate finite differencing is employed. storage requirements increase approximately as p2 \\+ n2, where p is the number of irregular boundary points and where n is the linear domain dimension. the preprocessing time (the capacitance matrix calculation) varies as pn2 log n, and the solution time varies as n2 log n. if the equations are to be solved repeatedly in the same geometry, but with different source or diffusion functions, the capacitance matrix need only be calculated once, and hence the algorithm is particularly efficient for such cases.  patrick f. cummins geoffrey k. vallis
performance evaluation of programs for certain bessel functions  this paper presents methods for performance evaluation of the k bessel functions. accuracy estimates are based on comparisons involving the multiplication theorem. some ideas for checking robustness are also given. the techniques used here are easily extended to the y bessel functions and, with a little more effort, to the i and j functions. details on a specific implementation for testing the k bessel functions are included.  w. j. cody l. stoltz
a global optimization algorithm using stochastic differential equations  sigma is a set of fortran subprograms for solving the global optimization problem, which implements a method founded on the numerical solution of a cauchy problem for a stochastic differential equation inspired by statistical mechanics.  this paper gives a detailed description of the method as implemented in sigma and reports the results obtained by sigma attacking, on two different computers, a set of 37 test problems which were proposed elsewhere by the present authors to test global optimization software.  the main conclusion is that sigma performs very well, solving 35 of the problems, including some very hard ones.  unfortunately, the limited results available to us at present do not appear sufficient to enable a conclusive comparison with other global optimization methods.  filippo aluffi-pentini valerio parisi francesco zirilli
on recursive calculation of the generalized inverse of a matrix  the generalized inverse of a matrix is an extension of the ordinary square matrix inverse which applies to any matrix (e.g., singular, rectangular). the generalized inverse has numerous important applications such as regression analysis, filtering, optimization and, more recently, linear associative memories. in this latter application known as distributed associative memory, stimulus vectors are associated with response vectors and the result of many associations is spread over the entire memory matrix, which is calculated as the generalized inverse. addition/deletion of new associations requires recalculation of the generalized inverse, which becomes computationally costly for large systems. a better solution is to calculate the generalized inverse recursively. the proposed algorithm is a modification of the well known algorithm due to rust et al. [2], originally introduced for nonrecursive computation. we compare our algorithm with greville's recursive algorithm and conclude that our algorithm provides better numerical stability at the expense of little extra computation time and additional storage.  saleem mohideen vladimir cherkassky
the traveling salesman problem in graphs with 3-edge cutsets  this paper analyzes decomposition properties of a graph that, when they occur, permit a polynomial solution of the traveling salesman problem and a description of the traveling salesman polytope by a system of linear equalities and inequalities. the central notion is that of a 3-edge cutset, namely, a set of 3 edges that, when removed, disconnects the graph. conversely, our approach can be used to construct classes of graphs for which there exists a polynomial algorithm for the traveling salesman problem. the approach is illustrated on two examples, halin graphs and prismatic graphs.  g. cornuejols d. naddef w. pulleyblank
computing the mdmt decomposition  the mdmt factorization of an n×n symmetric indefinite matrix a can be used to solve a linear system with a as the coefficient matrix. this factorization can be computed efficiently using an algorithm given in 1977 by bunch and kaufman. the lapack project has been implementing block versions of well-known algorithms for solving dense linear systems and eigenvalue problems. the block version of the mdmt decomposition algorithm in lapack requires the user to specify a block size b by supplying an n×b scratch array. it then makes (n/b 2)2/2 invocations of a matrix-matrix product subroutine with one matrix no larger than b×b, n2/(2b) b invocations of a matrix-vector product routine with a matrix no larger than b×b, and between n n/b and 2(n n/b) invocations of a matrix-vector product routine with matrices with less than b columns. because the user can query lapack about an optimal block size, our concern is focused on users who cannot change the amount of available scratch space or who neglect to use this facility and are unaware of a performance degradation with small block sizes. this article suggests two alternative algorithms. the first is a block algorithm requiring b×b scratch space and is about 5% slower than lapack's current block algorithm with large b. the user does not have to specify the block size. the second algorithm is a rejuvenation of an old implementation of the mdmt decomposition algorithm that requires n matrix- vector products. the performance of the various algorithms on a specific machine is dependent on the manufacturer's implementation of the different basic linear algebra subroutines that they each invoke. our data indicate that on the cray y-mp, alliant, and convex the time for the rejuvenated algorithm is either less than or within 10% of that of lapack's block algorithm with large b.  linda kaufman
algorithm 717; subroutines for maximum likelihood and quasi-likelihood estimation of parameters in nonlinear regression models  we present fortran 77 subroutines that solve statistical parameter estimation problems for general nonlinear models, e.g., nonlinear least-squares, maximum likelihood, maximum quasi-likelihood, generalized nonlinear least-squares, and some robust fitting problems. the accompanying test examples include members of the generalized linear model family, extensions using nonlinear predictors ("nonlinear glim"), and probabilistic choice models, such as linear-in- parameter multinomial probit models. the basic method, a generalization of the nl2sol algorithm for nonlinear least-squares, employs a model/trust-region scheme for computing trial steps, exploits special structure by maintaining a secant approximation to the second-order part of the hessian, and adaptively switches between a gauss-newton and an augmented hessian approximation. gauss- newton steps are computed using a corrected seminormal equations approach. the subroutines include variants that handle simple bounds on the parameters, and that compute approximate regression diagnostics.  david s. bunch david m. gay roy e. welsch
getting rid of correlations among pseudorandom numbers: discarding versus tempering  we consider the impact of discarding and tempering on modern huge period high speed linear generators, and illustrate how a simple strategy yields unexpected &amp;mdashh; and unwanted --- success in a fair coin gambling which is simulated by a recently proposed generator. it becomes clear that discarding is no general rule to get rid of unwanted correlations.  stefan wegenkittl makoto matsumoto