waashk/acm huggingface dataset:
a remark on algorithm 644: "a portable package for bessel functions of a complex argument and nonnegative order"  algorithm 644 computes all major bessel functions of a complex argument and of nonnegative order. single- precision routine cbesy and double-precision routine zbesy are modified to reduce the computation time for the y bessel function by approximately 25% over a wide range of arguments and orders. quick check (driver) programs that exercise the package are also modified to make tests more meaningful over larger regions of the complex plane.  d. e. amos
fitting "standard" distributions to data is necessarily good: dogma or myth?  this paper questions the conventional wisdom that "standard" distributions such as the normal, gamma, or beta families should necessarily be used to model inputs for simulation and proposes an alternative. relevant criteria are the quality of the fits and the impact of the input distributions on effective use of variance reduction techniques and on variate-generation speed. the proposed alternative, a "quasi-empirical" distribution, looks good on all these measures.  bennett l. fox
real values of the w-function  approximations for real values of w(x), where w is defined by solutions of w exp(w) = x, are presented. all of the approximations have maximum absolute (|w|>1) or relative (|w|<1) errors of o(10 4). with these approximations an efficient algorithm, consisting of a single iteration of a rapidly converging iteration scheme, gives estimates of w(x) accurate to at least 16 significant digits (15 digits if double precision is used). the fortran code resulting from the algorithm is written to account for the different floating-point- number mantissa lengths on different computers, so that w(x) is computed to the floating-point precision available on the host machine.  d. a. barry p. j. culligan-hensley s. j. barry
can any stationary iteration using linear information be globally convergent?  all known globally convergent iterations for the solution of a nonlinear operator equation (x) = 0 are either nonstationary or use nonlinear information. it is asked whether there exists a globally convergent stationary iteration which uses linear information. it is proved that even if global convergence is defined in a weak sense, there exists no such iteration for as simple a class of problems as the set of all analytic complex functions having only simple zeros. it is conjectured that even for the class of all real polynomials which have real simple zeros there does not exist a globally convergent stationary iteration using linear information.  g. w. wasilkowski
multicommodity flows in planar undirected graphs and shortest paths  this paper deals with the multicommodity flow problems for two classes of planar undirected graphs. the first class c12 consists of graphs in which each source- sink pair is located on one of two specified face boundaries. the second class c01 consists of graphs in which some of the source-sink pairs are located on a specified face boundary and all the other pairs share a common sink located on the boundary. we show that the multicommodity flow problem for a graph in c12 (resp. c01) can be reduced to the shortest path problem for an undirected (resp. a directed) graph obtained from the dual of the original undirected graph.  h suzuki t nishizeki n saito
algorithm 722; functions to support the ieee standard for binary floating- point arithmetic  this paper describes c programs for the support functions copysign(x,y), logb(x), scalb(x,n), nextafter(x,y), finite(x), and isnan(x) recommended in the appendix to the ieee standard for binary floating-point arithmetic. in the case of logb, the modified definition given in the later ieee standard for radix-independent floating-point arithmetic is followed. these programs should run without modification on most systems conforming to the binary standard.  w. j. cody jerome t. coonen
a fast adaptive grid scheme for elliptic partial differential equations  we describe the recursive subdivision (rs) method-an efficient and effective adaptive grid scheme for two-dimensional elliptic partial differential equations (pdes). the rs method generates a new grid by recursively subdividing a rectangular domain. we use a heuristic approach which attempts to equidistribute a given density function over the domain. the resulting grid is used to generate an adaptive grid domain mapping (agdm), which may be applied to transform the pde problem to another coordinate system. the pde is then solved in the transformed coordinate system using a uniform grid. we believe parallelism is most easily exploited when computations are carried out on uniform grids; the agdm framework allows the power of adaptation to be applied while still preserving this uniformity. our method generates good adaptive grid domain mappings at a small cost compared to the cost of the entire computation. we describe the rs algorithm in detail, briefly describe the agdm framework, and illustrate the effectiveness of our scheme on several realistic test problems.  calvin j. ribbens
the solution of almost block diagonal linear systems arising in spline collocation at gaussian points with monomial basis functions  numerical techniques based on piecewise polynomial (that is, spline) collation at gaussian points are exceedingly effective for the approximate solution of boundary value problems, both for ordinary differential equations and for time dependent partial differential equations. there are several widely available computer codes based on this approach, all of which have at their core a particular choice of basis representation for the piecewise polynomials used to approximate the solutions. until recently, the most popular approach was to use a b-spline representation, but it has been shown that the b-spline basis is inferior, both in operation counts and conditioning, to a certain monomial basis, and the latter has come more into favor. in this paper, we describe a linear algebraic equations which arise in spline collocation at gaussian points with such a monomial basis. it is shown that the new package, which implements an alternate column and row pivoting algorithm, is a distinct improvement over existing packages from the points of view of speed and storage requirements. in addition, we describe a second package, an important special case of the first, for solving the almost block diagonal systems which arise when condensation is applied to the systems arising in spline collocation at gaussian points, and also in other methods for solving two- point boundary value problems, such as implicit runge-kutta methods and multiple shooting.  gouad majaess patrick keast graeme fairweather karin r. bennett
collocation software for second-order elliptic partial differential equations  we consider the collocation method for linear, second-order elliptic problems on rectangular and general two-dimensional domains. an overview of the method is given for general domains, followed by a discussion of the improved efficiencies and simplifications possible for rectangular domains. a very- high-level description is given of three specific collocation algorithms that use hermite bicubic basic functions, (1) gencol (collocation on general two- dimensional domains), (2) hermcol (collocation on rectangular domains with general linear boundary conditions), and (3) intcol (collocation on rectangular domains with uncoupled boundary conditions). the linear system resulting from intcol has half the bandwidth of that from hermcol, which provides substantial benefit in solving the system. we provide some examples showing the range of applicability of the algorithms and some performance profiles illustrating their efficiency. fortran implementations of these algorithms are given in the companion papers [10, 11].  e. n. houstis w. f. mitchell j. r. rice
algorithm 706; dcutri: an algorithm for adaptive cubature over a collection of triangles  an adaptive algorithm for computing an approximation to the integral of each element in a vector function f(x,y) over a two-dimensional region made up of triangles is presented. a fortran implementation of the algorithm is included. the basic cubature rule used over each triangle is a 37-point symmetric rule of degree 13. based on the same evaluation points the local error for each element in the approximation vector and for each triangle is computed using a sequence of null rule evaluations. a sophisticated error-estimation procedure tries, in a cautious manner, to decide whether we have asymptotic behavior locally for each function. different actions are taken depending on that decision, and the procedure takes advantage of the basic rule's polynomial degree when computing the error estimate in the asymptotic case.  jarle berntsen terje o. espelid
fast pseudorandom generators for normal and exponential variates  fast algorithms for generating pseudorandom numbers from the unit-normal and unit- exponential distributions are described. the methods are unusual in that they do not rely on a source of uniform random numbers, but generate the target distributions directly by using their maximal-entropy properties. the algorithms are fast. the normal generator is faster than the commonly used unix library uniform generator "random" when the latter is used to yield real values. their statistical properties seem satisfactory, but only a limited suite of tests has been conducted. they are written in c and as written assume 32-bit integer arithmetic. the code is publicly available as c source and can easily be adopted for longer word lengths and/or vector processing.  c. s. wallace
algorithm 690; chebyshev polynomial software for elliptic-parabolic systems of pdes  pdecheb is a fortran 77 software package that semidiscretizes a wide range of time-dependent partial differential equations in one space variable. the software implements a family of spacial discretization formulas, based on piecewise chebyshev polynomial expansions with c0 continuity. the package has been designed to be used in conjunction with a general integrator for initial value problems to provide a powerful software tool for the solution of parabolic-elliptic pdes with coupled differential algebraic equations. examples are provided to illustrate the use of the package with the dassl d.a.e integrator of petzold [18].  m. berzins p. m. dew
automatic building of graphs for rectangular dualisation  rectangular dualisation is a technique used to generate rectangular topologies for use in top-down floorplanning of integrated circuits. this paper presents an efficient algorithm that transforms an arbitrary graph, representing a custom integrated circuit, into one suitable for rectangular dualisation. the algorithm makes use of efficient techniques in graph processing such as planar embedding and introduces a novel procedure to transform a tree of biconnected sub-graphs into a block neighbourhood graph that is a path.  marwan a. jabri
walsh-spectral test for gfsr pseudorandom numbers  by applying weyl's criterion for k-distributivity to gfsr sequences, we derive a new theoretical test for investigating the statistical property of gfsr sequences. this test provides a very useful measure for examining the k-distribution, that is, the statistical independence of the k-tuple of successive terms of gfsr sequences. in the latter half of this paper, we describe an efficient procedure for performing this test and furnish experimental results obtained from applying it to several gfsr generators with prime period lengths.  shu tezuka
best "ordering" for floating-point addition  this correspondence examines the influence of the summation order on the numerical accuracy of the resulting sum when the addition is performed using floating-point, finite- precision arithmetic. a simple statistical model is used to find the relative performance of various addition procedures. it is shown that phrasing the question in terms of finding a best ordering is overly restrictive since the most natural and accurate procedures for performing the addition utilize the storage of intermediate sums as well as performing orderings.  t. g. robertazzi s. c. schwartz
an adaptive mesh-moving and local refinement method for time-dependent partial differential equations  we discuss mesh-moving, static mesh- regeneration, and local mesh-refinement algorithms that can be used with a finite difference or finite element scheme to solve initial-boundary value problems for vector systems of time-dependent partial differential equations in two space dimensions and time. a coarse base mesh of quadrilateral cells is moved by an algebraic mesh-movement function so as to follow and isolate spatially distinct phenomena. the local mesh- refinement method recursively divides the time step and spatial cells of the moving base mesh in regions where error indicators are high until a prescribed tolerance is satisfied. the static mesh-regeneration procedure is used to create a new base mesh when the existing one becomes too distorted. the adaptive methods have been combined with a maccormack finite difference scheme for hyperbolic systems and an error indicator based upon estimates of the local discretization error obtained by richardson extrapolation. results are presented for several computational examples.  david c. arney joseph e. flaherty
factoring a binary polynomial of degree over one million on 22 may 2000, the factorization of a pseudorandom polynomial of degree 1 048 543 over the binary field z2 was completed on a 4-processor linux pc, using roughly 100 cpu-hours. the basic approach is a combination of the factorization software bipolar and a parallel version of cantor's multiplication algorithm. the pub-library (paderborn university bsp library) is used for the implementation of the parallel communication. olaf bonorden joachim von zur gathen jurgen gerhard olaf muller
generating multivariate distributions for statistical applications  methods for generating random vectors from multi- variate distributions are required in a variety of statistical research contexts. examples of topics include examination of the robustness of multivariate tests such as roy's largest root test, assessment of error rates in discriminant analysis, and comparing multivariate goodness-of-fit methods. this presentation assimilates the material in a coherent framework and identifies some useful generation algorithms. the slant is admittedly to statistical applications but this does not preclude its use in other areas.  mark e. johnson
a note on the recursive calculation of incomplete gamma functions  it is known that the recurrence relation for incomplete gamma functions {γ(a \\+ n, x)}, 0 ≤ a < 1, n = 0, 1, 2 ..., when x is positive, is unstable---more so the larger x. nevertheless, the recursion can be used in the range 0 ≤ n ≤ x practically without error growth, and in larger ranges 0 ≤ n ≤ n with a loss of accuracy that can be controlled by suitably limiting n.  walter gautschi
algebraic methods in the theory of lower bounds for boolean circuit complexity  we use algebraic methods to get lower bounds for complexity of different functions based on constant depth unbounded fan-in circuits with the given set of basic operations. in particular, we prove that depth k circuits with gates not, or and modp where p is a prime require exp( (n1/2k)) gates to calculate modr functions for any r pm. this statement contains as special cases yao's parity result [ ya 85 ] and razborov's new majority result [ra 86] (modm gate is an oracle which outputs zero, if the number of ones is divisible by m).  r. smolensky
on the storage requirement in the out-of-core multifrontal method for sparse factorization  two techniques are introduced to reduce the working storage requirement for the recent multifrontal method of duff and reid used in the sparse out-of-core factorization of symmetric matrices. for a given core size, the reduction in working storage allows some large problems to be solved without having to use auxiliary storage for the working arrays. even if the working arrays exceed the core size, it will reduce the amount of input- output traffic necessary to manipulate the working vectors. experimental results are provided to demonstrate significant storage reduction on practical problems using the proposed techniques.  joseph w. h. liu
on the expected behavior of disjoint set union algorithms  we show that the expected time of the weighted quickfind (qfw) disjoint set union and find algorithm to perform (n - 1) randomly chosen unions is cn + o(n/log n), where c = 2.0847 …. this implies, through an observation of tarjan and van leeuwen, linear expected time bounds to perform o(n) unions and finds for a class of other union -find algorithms. we also prove that the expected time of the unweighted quickfind (qf) algorithm is n2/8 + o(n(log n)2), and set the several related open questions of knuth and schonhage.  b bollobás i simon
a quadratic-tensor model algorithm for nonlinear least-squares problems with linear constraints  a new algorithm is presented for solving nonlinear least-squares and nonlinear equation problems. the algorithm is based on approximating the nonlinear functions using the quadratic-tensor model proposed by schnabel and frank. the problem statement may include simple bounds or more general linear constraints on the unknowns. the algorithm uses a trust-region defined by a box containing the current values of the unknowns. the objective function (euclidean length of the functions) is allowed to increase at intermediate steps. these increases are allowed as long as our predictor indicates that a new set of best values exists in the trust-region. there is logic provided to retreat to the current best values, should that be required. the computations for the model-problem require a constrained nonlinear least-squares solver. this is done using a simpler version of the algorithm. in its present form the algorithm is effective for problems with linear constraints and dense jacobian matrices. results on standard test problems are presented in the appendix. the new algorithm appears to be efficient in terms of function and jacobian evaluations.  r. j. hanson fred t. krogh
reliable solution of special event location problems for odes  computing the solution of the initial value problem in ordinary differential equations (odes) may be only part of a larger task. one such task is finding where an algebraic function of the solution (an event function) has a root (an event occurs). this is a task which is difficult both in theory and in software practice. for certain useful kinds of event functions, it is possible to avoid two fundamental difficulties. it is described how to achieve the reliable solutions of such problems in a way that allows the capability to be grafted onto popular codes for the initial value problem.  l. f. shampine i. gladwell r. w. brankin
automatic sampling with the ratio-of-uniforms method  applying the ratio-of-uniforms method for generating random variates results in very efficient, fast, and easy-to-implement algorithms. however parameters for every particular type of density must be precalculated analytically. in this article we show, that the ratio-of-uniforms method is also useful for the design of a black-box algorithm suitable for a large class of distributions, including all with log-concave densities. using polygonal envelopes and squeezes results in an algorithm that is extremely fast. in opposition to any other ratio-of-uniforms algorithm the expected number of uniform random numbers is less than two. furthermore, we show that this method is in some sense equivalent to transformed density rejection.  josef leydold
a note on the quality of random variates generated by the ratio of uniforms method  the one-dimensional distribution of pseudorandom numbers generated by the ratio of uniforms method using linear congruential generators (lcgs) as the source of uniform random number is investigated in this note. due to the two- dimensional lattice structure of lcgs there is always a comparable large gap without a point in the one-dimensional distribution of any ratio of uniforms method. lower bounds for these probabilities only depending on the modulus and the beyer quotient of the lcg are proved for the case that cauchy normal or exponential random numbers are generated. these bounds justify the recommendation not to use the ratio of uniform method combined with lcgs.  wolfgang hörmann
a modified adams method for nonstiff and mildly stiff initial value problems  adams predictor-corrector methods, and explicit runge--kutta formulas, have been widely used for the numerical solution of nonstiff initial value problems. both of these classes of methods have certain drawbacks, however, and it has long been the aim of numerical analysts to derive a class of formulas that has the advantages of both adams and runge--kutta methods and the disadvantages of neither! in this paper we derive a class of modified adams formulas that attempts to achieve this aim. when used in a certain precisely defined predictor-corrector mode, these new formulas require three function evaluations per step, but have much better stability than adams formulas. this improved stability makes the modified adams formulas particularly effective for mildly stiff problems, and some numerical evidence of this is given. we also consider the performance of the new class of methods on the well-known detest test set to show their potential on general nonstiff initial value problems.  j. r. cash s. semnani
a faster deterministic maximum flow algorithm  we describe a deterministic version of a 1990 cheriyan, hagerup, and mehlhorn randomized algorithm for computing the maximum flow on a directed graph with n nodes and m edges which runs in time o(mn \\+ n2+ε, for any constant ε. this improves upon alon's 1989 bound of o(mn \\+ n8/3log n) [a] and gives an o(mn) deterministic algorithm for all m > n1+ε. thus it extends the range of m/n for which an o(mn) algorithm is known, and matches the 1988 algorithm of goldberg and tarjan [gt] for smaller values of m/n.  v. king s. rao r. tarjan
table-driven implementation of the exponential function in ieee floating-point arithmetic  algorithms and implementation details for the exponential function in both single- and double-precision of ieee 754 arithmetic are presented here. with a table of moderate size, the implementations need only working-precision arithmetic and are provably accurate to within 0.54 ulp as long as the final result does not underflow. when the final result suffers gradual underflow, the error is still no worse than 0.77 ulp.  ping- tak peter tang
an algorithm for building rectangular floor-plans  previous reports [1, 3] have shown how to build an optimal floor-plan assembly starting with a planar structure graph in terms of components and their connections. the existing methods are based on exhaustively inspecting all possible rectangular duals until an optimal one is found. however, expensive computational resources are wasted when no rectangular dual exists.  this paper presents a graph-theoretical formulation for the existence of rectangular floor-plans. it is shown that any triangulated graph (planar graph with all regions triangular) admits a rectangular dual if and only if it does not contain complex triangular faces. this result is the basis of a fast algorithm for checking admissibility of solutions.  sany m. leinwand yen-tai lai
implementing gauss jordan on a hypercube multicomputer  we consider the solution of dense algebraic systems on the ncube hypercube via the gauss jordan method. advanced loop interchange techniques are used to determine the appropriate algorithm for mimd architectures. for a computer with p = n processors, we show that gauss jordan is competitive to gaussian elimination when pivoting is not used. we experiment with three mappings of columns to processors: block, wrap and reflection. we demonstrate that load balancing the processors results in a considerable reduction of execution time.  a. gerasoulis n. missirlis i. nelken r. peskin