waashk/acm huggingface dataset:
efficient and portable combined random number generators  in this paper we present an efficient way to combine two or more multiplicative linear congruential generators (mlcgs) and propose several new generators. the individual mlcgs, making up the proposed combined generators, satisfy stringent theoretical criteria for the quality of the sequence they produce (based on the spectral test) and are easy to implement in a portable way. the proposed simple combination method is new and produces a generator whose period is the least common multiple of the individual periods. each proposed generator has been submitted to a comprehensive battery of statistical tests. we also describe portable implementations, using 16-bit or 32-bit integer arithmetic. the proposed generators have most of the beneficial properties of mlcgs. for example, each generator can be split into many independent generators and it is easy to skip a long subsequence of numbers without doing the work of generating them all.  p. l'ecuyer
an optimal randomized logarithmic time connectivity algorithm for the erew pram (extended abstract)  improving a long chain of works we obtain a randomized erew pram algorithm for finding the connected components of a graph g=(v,e) with n vertices and m edges in o(log n) time using an optimal number of o((m+n)/log n) processors. the result returned by the algorithm is always correct. the probability that the algorithm will not complete in o(log n) time is at most -c for any desired c > 0.  the best deterministic erew pram connectivity algorithm, obtained by chong and lam, runs in o(log n log log n) time using m \\+ n processors.  shay halperin uri zwick
algorithm 702; tnpack - a truncated newton minimization package for large- scale problems: i. algorithm and usage  we present a fortran package of subprograms for minimizing multivariate functions without constraints by a truncated newton algorithm. the algorithm is especially suited for problems involving a large number of variables. truncated newton methods allow approximate, rather than exact, solutions to the newton equations. truncation is accomplished in the present version by using the preconditioned conjugate gradient algorithm (pcg) to solve approximately the newton equations. the preconditioner m is factored in pcg using a sparse modified cholesky factorization based on the yale sparse matrix package. in this paper we briefly describe the method and provide details for program usage.  tamar schlick aaron fogelson
solving systems of nonlinear equations using the nonzero value of the topological degree  two algorithms are described here for the numerical solution of a system of nonlinear equations f(x) = ,  q=0,0, ,0∈ r , and f is a given continuous mapping of a region  d in  rn into  rn . the first algorithm locates at least one root of the sy stem within n-dimensional polyhedron, using the non zero value of the topological degree of f at relative to the polyhedron; the second algorithm applies a new generalized bisection method in order to compute an approximate solution to the system. teh size of the original n-dimensional polyhedron is arbitrary, and the method is globally convergent in a residual sense.  these algorithms, in the various function evaluations, only make use of the algebraic sign of f and do not require computations of the topological degree. moreover, they can be applied to nondifferentiable continuous functions f and do not involve derivatives of f or approximations of such derivatives.  michael n. vrahatis
algorithm 773: ssrfpack: interpolation of scattered data on the surface of a sphere with a surface under tension  ssrfpack is a fortran 77 software package that constructs a smooth interpolatory or approximating surface to data values associated with arbitrarily distributed points on the surface of a sphere. it employs automatically selected tension factors to preserve shape properties of the data and avoid overshoot and undershoot associated with steep gradients.  robert j. renka
algorithm 643: fexact: a fortran subroutine for fisher's exact test on unordered r c contingency tables  the computer code for mehta and patel's (1983) network algorithm for fisher's exact test on unordered r×c contingency tables is provided. the code is written in double precision fortran 77. this code provides the fastest currently available method for executing fisher's exact test, and is shown to be orders of magnitude superior to any other available algorithm. many important details of data structures and implementation that have contributed crucially to the success of the network algorithm are recorded here.  cyrus r. mehta nitin r. patel
a partial pivoting strategy for sparse symmetric matrix decomposition  it is well known that the partial pivoting strategy by bunch and kaufman is very effective forfactoring dense symmetric indefinite matrices using the diagonal pivoting method. in this paper, westudy a threshold version of the strategy for sparse symmetric matrix decomposition. the use of thisscheme is explored in the multifrontal method of duff and reid for sparse indefinite systems.experimental results show that it is at least as effective as the existing pivoting strategy used in thecurrent multifrontal implementation.  joseph w. h. liu
algorithm 711; btn: software for parallel unconstrained optimization  btn is a collection of fortran subroutines for solving unconstrained nonlinear optimization problems. it currently runs on both intel hypercube computers (distributed memory) and sequent computers (shared memory), and can take advantage of vector processors if they are available. the software can also be run on traditional computers to simulate the performance of a parallel computer. btn is a general-purpose algorithm, capable of solving problems with a large numbers of variables and suitable for users inexperienced with parallel computing. it is designed to be as easy to use as traditional algorithms for this problem, requiring only that a (scalar) subroutine be provided to evaluate the objective function and its gradient vector of first derivatives. the algorithm is based on a block truncated-newton method. truncated-newton methods obtain the search direction by approximately solving the newton equations via some iterative method. the particular method used in btn is a block version of the lanczos method, which is numerically stable for nonconvex problems. in addition to the optimization software, a parallel derivative checker is also provided.  stephen g. nash ariela sofer
small sets supporting fary embeddings of planar graphs  answering a question of rosenstiehl and tarjan, we show that every plane graph with n vertices has a fary embedding (i.e., straight-line embedding) on the 2n \\- 4 by n \\- 2 grid and provide an (n) space, (n log n) time algorithm to effect this embedding. the grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. on the other hand we show that any set f, which can support a fary embedding of every planar graph of size n, has cardinality at least n \\+ (1 -  (1)) n which settles a problem of mohar.  hubert de fraysseix jános pach richard pollack
software for estimating sparse hessian matrices  the solution of a nonlinear optimization problem often requires an estimate of the hessian matrix for a function f. in large scale problems, the hessian matrix is usually sparse, and then estimation by differences of gradients is attractive because the number of differences can be small compared to the dimension of the problem. in this paper we describe a set of subroutines whose purpose is to estimate the hessian matrix with the least possible number of gradient evaluations.  thomas f. coleman burton s. garbow jorge j. more
algorithm 731; a moving-grid interface for systems of one-dimensional time- dependent partial differential equations  in the last decade, several numerical techniques have been developed to solve time-dependent partial differential equations (pdes) in one dimension having solutions with steep gradients in space and in time. one of these techniques, a moving-grid method based on a lagrangian description of the pde and a smoothed-equidistribution principle to define the grid positions at each time level, has been coupled with a spatial discretization method that automatically discreizes the spatial part of the user-defined pde following the method of lines approach. we supply two fortran subroutines, cwresu and cwresx, which compute the residuals of the differential algebraic equations (dae) system obtained from semidiscretizing, respectively, the pde and the set of moving-grid equations. these routines are combined in an enveloping routine skmres, which delivers the residuals of the complete dae system. to solve this stiff, nonlinear dae system, a robust and efficient time-integrator must be applied, for example, a bdf method such as implemented in the dae solvers sprint [berzins and furzeland 1985; 1986; berzins et al. 1989] and dassl [brenan et al. 1989; petzold 1983]. some numerical examples are shown to illustrate the simple and effective use of this software interface.  j. g. blom p. a. zegeling
implementation of hopf and double-hopf continuation using bordering methods  we discuss the computational study of curves of hopf and double-hopf points in the software package content developed at cwi, amsterdam. these are important points in the numerical study of dynamical systems characterized by the occurrence of one or two conjugate pairs of pure imaginary eigenvalues in the spectrum of the jacobian matrix. the bialternate product of matrices is extensively used in three codes for the numerical continuation of curves of hopf points and in one for the continuation of curves of double-hopf points. in the double-hopf and two of the single-hopf cases this is combined with a bordered matrix method. we use this software to find special points on a hopf curve in a model of chemical oscillations and by computing a hopf and a double-hopf curve in a realistic model of a neuron.  w. govaerts yu. a. kuznetsov b. sijnave
algorithm 742; l2cxft: a fortran subroutine for least-squares data fitting with nonnegative second divided differences  a fortran subroutine applies the method of demetriou and powell [1991] to restore convexity in n measurements of a convex function contaminated by random errors. the method minimizes the sum of the squares of the errors, subject to nonnegativity of second divided differences, in two phases. first, an approximation close to the optimum is derived in o(n) operations. then, this approximation is used as the starting point of a dual-feasible quadratic programming algorithm that completes the calculation of the optimum. the constraints allow b-splines to be used, which reduce the problem to an equivalent one with fewer variables where the knots of the splines are determined automatically from the data points due to the constraint equations. the subroutine benefits from this reduction, since common submatrices that occur during the calculation are updated suitably. iterative refinement improves the accuracy of some calculations when round-off errors accumulate. the subroutine has been applied to a variety of data having substantial differences and has performed fast and stably even for small data spacing, large n, and single-precision arithmetic. driver programs and examples with output are provided to demonstrate the use of the subroutine.  i. c. demetriou
a numerical technique for analytic continuation (abstract only)  the principle of analytic continuation for a complex analytic function is well known. a numerical technique which directly employs the cauchy-riemann equations will be presented for performing analytic continuation in a region. the technique can be readily implemented in a concurrent programming environment in which the region is subdivided with a grid and a process created at each grid position. since any process can transition to its final state as soon as its immediate neighbors have obtained a suitable configuration, analytic continuation is able to "flow" naturally throughout the region. this work is motivated by considerations of adaptability to various regions and not by efficiency. however, the nature of the interprocess communication is critical. this is also described.  mark temte
algorithm 689; discretized collocation and iterated collocation for nonlinear volterra integral equations of the second kind  this paper describes a fortran code for calculating approximate solutions to systems of nonlinear volterra integral equations of the second kind. the algorithm is based on polynomial spline collocation, with the possibility of combination with the corresponding iterated collocation. it exploits certain local superconvergence properties for the error estimation and the stepsize strategy.  j. g. blom h. brunner
a block 6(4) runge-kutta formula for nonstiff initial value problems  a new selection is made for an efficient two-step block runge-kutta formula of order 6. the new formula is developed using some of the efficiency criteria recently investigated by shampine, and as a result, a block formula with much improved performance is obtained. an important property of this new formula is that there is a "natural" interpolating polynomial available. this can be used to compute approximate solution values at off-step points without the need to compute any additional function evaluations. the quality of this interpolant is examined, and it is shown to have certain desirable properties. the performance of the new block runge- kutta formula is evaluated using the detest test set and is shown to be more efficient than certain other standard runge-kutta formulas for this particular test set.  j. r. cash
lower bounds on the complexity of graph properties  in this simple model, a decision tree algorithm must determine whether an unknown digraph on nodes {1, 2, …, n} has a given property by asking questions of the form "is edge  in the graph?". the complexity of a property is the number of questions which must be asked in the worst case.  aanderaa and rosenberg conjectured that any monotone, nontrivial, (isomorphism-invariant) n-node digraph property has complexity (n2). this bound was proved by rivest and vuillemin and subsequently improved to  n2/4+ (n2). in part i, we give a bound of n2< /supscrpt>/2+ (n& lt;supscrpt>2). whether these properties are evasive remains open.  in part ii, we investigate the power of randomness in recognizing these properties by considering randomized decision tree algorithms in which coins may be flipped to determine the next edge to be queried. yao's lower bound on the randomized complexity of any monotone nontrivial graph property is improved from (nlog& lt;supscrpt>1/12n) to (n5/4), and improved bounds for the complexity of monotone, nontrivial bipartite graph properties are shown.  valerie king
fixed versus variable order runge-kutta  popular codes for the numerical solution of nonstiff ordinary differential equations (odes) are based on a (fixed order) runge-kutta method, a variable order adams method, or an extrapolation method. extrapolation can be viewed as a variable order runge-kutta method. it is plausible that variation of order could lead to a much more efficient runge-kutta code, but numerical comparisons have been contradictory.  we reconcile previous comparisons by exposing differences in testing methodology and incompatibilities of the implementations tested. an experimental runge-kutta code is compared to a state-of-the-art extrapolation code. with some qualifications, the extrapolation code shows no advantage. extrapolation does not appear to be a particularly effective way to vary the order of runge-kutta methods. although an acceptable way to solve nonstiff problems, our tests raise the question as to whether there is any point in pursuing it as a separate method.  l. f. shampine l. s. baca
a primal null-space affine-scaling method  this article develops an affine-scaling method for linear programming in standard primal form. its descent search directions are formulated in terms of the null-space of the linear programming matrix, which, in turn, is defined by a suitable basis matrix. we describe some basic properties of the method and an experimental implementation that employs a periodic basis change strategy in conjunction with inexact computation of the search direction by an iterative method, specifically, the conjugate-gradient method with diagonal preconditioning. the result of a numerical study on a number of nontrivial problems representative of problems that arise in practice are reported and discussed.  a key advantage of the primal null-space affine- scaling method is its compatibility with the primal simplex method. this is considered in the concluding section, along with implications for the development of a more practical implementation.  k. kim j. l. nazareth
a schwarz splitting variant of cubic spline collocation methods for elliptic pdes  we consider the formulation of the schwarz alternating method for a new class of elliptic cubic spline collocation discretization schemes. the convergence of the method is studied using jacobi and gauss-seidel iterative methods for implementing the interaction among subdomains. the schwarz cubic spline collocation (scsc) method is formulated for hypercube architectures and implemented on the ncube (128 processors) machine. the performance and convergence of the hypercube scsc algorithm is studied with respect to domain partition and subdomain overlapping area. the numerical results indicate that the partition and mapping of the scsc on the ncube is almost optimal while the speedup obtained is similar to other domain decomposition techniques.  e. n. houstis j. r. rice e. a. vavalis
remarks on implementation of _o_(_n_1/2τ) assignment algorithms  we examine an implementation and a number of 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 on1/2` 4;) behavior, where the matrix is of order n with τ entries. we compare the best of these with an efficient implementation of an algorithm whose worst-case behavior is o< ;/italic>(nτ).  iain s. duff torbjörn wiberg
determination of maximal symmetry groups of classes of differential equations  a symmetry of a differential equation is a transformation which leaves invariant its family of solutions. as the functional form of a member of a class of differential equations changes, its symmetry group can also change.  we give an algorithm for determining the structure and dimension of the symmetry group(s) of maximal dimension for classes of partial differential equations. it is based on the application of differential elimination algorithms to the linearized equations for the unknown symmetries. existence and uniqueness theorems are applied to the output of these algorithms to give the dimension of the maximal symmetry group.  classes of differential equations considered include ode of form uxx = (x, u, ux), reaction-diffusion systems of form ut \\- uxx = (u, v), vt \\- vxx = g(u, v), and nonlinear telegraph systems of form vt = ux, vx = c(u, x) ;ux \\+ b(u, x).  gregory j. reid allan d. wittkopf
simulation in exponential families  an acceptance-rejection algorithm for the simulation of random variables in statistical exponential families is described. this algorithm does not require any prior knowledge of the family, except sufficient stati stics and the value of the parameter. it allows simulation from many members of the exponential family. we present some bounds on computing time, as well as the main properties of the empirical measures of samples simulated by our methods (functional glivenko-cantelli and central limit theorems). this algorithm is applied in order to evaluate the distribution of m-estimators under composite alternatives; we also propose its use in bayesian statistics in order to simulate from posterior distributions.  philippe barbe michel broniatowski
on the statistical independence of nonlinear congruential pseudorandom numbers  recently, several nonlinear congruential methods for generating uniform pseudorandom numbers have been proposed and analysed. in the present note, further statistical independence properties of a general class of nonlinear congruential pseudorandom number generators are established. the results that are obtained are essentially best possible in an asymptotic sense and show that the generated pseudorandom numbers model truly random numbers very closely in terms of asymptotic discrepancy.  jurgen eichenauer- herrmann harald niederreiter
toward parallel mathematical software for elliptic partial differential equations  three approaches to parallelizing important components of the mathematical software package ellpack are considered: an explicit approach using compiler directives available only on the target machine, an automatic approach using an optimizing and parallelizing precompiler, and a two-level approach based on extensive use of a set of low level computational kernels. the focus is on shared memory architectures. each approach to parallelization is described in detail, along with a discussion of the effort involved. performance on a test problem, using up to sixteen processors of a sequent symmetry s81, is reported and discussed. implications for the parallelization of a broad class of mathematical software are drawn.  calvin j. ribbens layne t. watson colin desa
data-streams and histograms  histograms have been used widely to capture data distribution, to represent the data by a small number of step functions. dynamic programming algorithms which provide optimal construction of these histograms exist, albeit running in quadratic time and linear space. in this paper we provide linear time construction of 1 + ε approximation of optimal histograms, running in polylogarithmic space.  our results extend to the context of data-streams, and in fact generalize to give 1 + ε approximation of several problems in data-streams which require partitioning the index set into intervals. the only assumptions required are that the cost of an interval is monotonic under inclusion (larger interval has larger cost) and that the cost can be computed or approximated in small space. this exhibits a nice class of problems for which we can have near optimal data-stream algorithms.  sudipto guha nick koudas kyuseok shim
interpolatory integration formulas for optimal composition  a set of symmetric, closed, interpolatory integration formulas on the interval [-1, 1] with positive weights and increasing degree of precision is introduced. these formulas, called recursive monotone stable (rms) formulas, allow applying higher order or compound rules without wasting previously computed functional values. an exhaustive search shows the existence of 27 families of rms formulas, stemming from the simple trapezoidal rule.  paola favati grazia lotti francesco romani
fast hardware random number generator for the tausworthe sequence  many simulation programs require m-dimensional uniformly distributed random numbers. a linear recurrence modulo two generator, based on n-bits and producing l-bit numbers (l ≤ n), according to tausworthe theory, may yield a sequence of m-tuples uniformly distributed in m (n/l) dimensions. when using software computing algorithms on a binary computer, for large n (e.g. n 159), the generation speed is for many purposes too slow. to overcome this disadvantage we present a new concept of a hardware random number generator, to give the tausworthe sequence with high generation speed independent of the number of bits per word n. for a 32-bit data word computer we have performed statistical tests on three generators, two of them gave good results.  meir barel