waashk/acm huggingface dataset:
a portable random number generator well suited for the rejection method  up to now, all known efficient portable implementations of linear congruential random number generators with modulus 231 \\-- 1 have worked only with multipliers that are small compared with the modulus. we show that for nonuniform distributions, the rejection method may generate random numbers of bad qualify if combined with a linear congruential generator with small multiplier. a method is described that works for any multiplier smaller than 230. it uses the decomposition of multiplier and seed in high-order and low- order bits to compute the upper and lower half of the product. the sum of the two halfs gives the product of multiplier and seed modulo 221 \\-- 1. coded in ansi-c and fortran77 the method results in a portable implementation of the linear congruential generator that is as fast or faster than other portable methods.  w. hörmann g. derflinger
algorithm 705; a fortran-77 software package for solving the sylvester matrix equation axbt \\+ cxdt = e  this paper documents a software package for solving the sylvester matrix equation (1) axbt \\+ cxdt = e  all quantities are real matrices; a and c are m x n; b and d are m x n; and x and e are m x n. the unknown is x. two symmetric forms of eq. (1) are treated separately for efficiency. they are the continuous-time symmetric sylvester equation (2) axet \\+ exat \\+ c = 0 and the discrete time equation (3) axat \\+ c = 0, for which a, e, and c is symmetric. the software also provides a means for estimating the condition number of these three equations. the algorithms employed are more fully described in an accompanying paper [3].  judith d. gardiner matthew r. wette alan j. laub james j. amato cleve b. moler
graphs that are almost binary trees (preliminary version)  this paper studies embeddings of graphs in binary trees. the cost of such an embedding is the maximum distance in the binary tree between images of adjacent graph vertices. several techniques for bounding the costs of such embeddings from above are derived; notable among these is an algorithm for embedding any outerplanar graph in a binary tree with a cost that is within a factor of 3 of optimal. a number of techniques for bounding the costs of such embeddings from below are developed; notable here are two techniques for inferring the presence of large separators in graphs. finally, a number of characterizations are established of those families of graphs that are almost binary trees, in the sense that every graph in the family is embeddable in a binary tree within bounded cost.  hong jia-wei arnold l. rosenberg
latin supercube sampling for very high-dimensional simulations  this article introduces latin supercube sampling (lss) for very high- dimensional simulations such as arise in particle transport, finance, and queueing. lss is developed as a combination of two widely used methods: latin hypercube sampling (lhs) and quasi-monte carlo (qmc). in lss, the input variables are grouped into subsets, and a lower-dimensional qmc method is used within each subset. the qmc points are presented in random order within subsets. qmc methods have been observed to lose effectiveness in high- dimensional problems. this article shows that lss can extend the benefits of qmc to much higher dimensions, when one can make a good grouping of input variables. some suggestions for grouping variables are given for the motivating examples. even a poor grouping can still be expected to do as well as lhs. the article also extends lhs and lss to infinite-dimensional problems. the paper includes a survey of qmc methods, randomized versions of them (rqmc), and previous methods for extending qmc to higher dimensions. furthermore it shows that lss applied with rqmc is more reliable than lss with qmc.  art b. owen
new nag library software for first-order partial differential equations  new nag fortran library routines are described for the solution of systems of nonlinear, first-order, time-dependent partial differential equations in one space dimension, with scope for coupled ordinary differential or algebraic equations. the method-of-lines is used with spatial discretization by either the central-difference keller box scheme or an upwind scheme for hyperbolic systems of conservation laws. the new routines have the same structure as existing library routines for the solution of second-order partial differential equations, and much of the existing library software is reused. results are presented for several computational examples to show that the software provides physically realistic numerical solutions to a challenging class of problems.  s. v. pennington m. berzins
algorithm 812: bpoly: an object-oriented library of numerical algorithms for polynomials in bernstein form  the design, implementation, and testing of a c++ software library for univriate polynomials in bernstein form is described. by invoking the class environment and operator overloading, each polynomial in an expression is interpreted as an object compatible with the arithmetic operations and other common functions (subdivision, degree, elevation, differentiation and integration, compoistion, greatest common divisor, real-root solving, etc.) for polynomials in bernstein form. the library allows compact and intuitive implementation of lengthy manipulation of bernstein-form polynomials, which often arise in computer graphics and computer-aided design and manufacturing applications. a series of empirical tests indicates that the library functions are typically very accurate and reliable, even for polynomials of surprisingly high degree.  yi-feng tsai rida t. farouki
a reservation based cyclic server queue with limited service  in this paper, we examine a problem which is an extension of the limited service in a queueing system with a cyclic server. in this service mechanism, each queue, after receiving service in cycle j, makes a reservation for its service requirement in cycle j \\+ 1. in this paper, we consider symmetric case only, i.e., the arrival rates to all the queues are the same. the main contribution to queueing theory is that we propose an approximation for the queue length and sojourn-time distributions for this discipline. most approximate studies on cyclic queues, which have been considered before, examine the means only. our method is an iterative one, which we prove to be convergent by using stochastic dominance arguments. we examine the performance of our algorithm by comparing it to simulations and show that the results are very good.  duan-shin lee bhaskar sengupta
properly rounded variable precision square root  the square root function presented here returns a properly rounded approximation to the square root of its argument, or it raises an error condition if the argument is negative. properly rounded means rounded to the nearest, or to nearest even in case of a tie. it is variable precision in that it is designed to return a p-digit approximation to a p-digit argument, for any p > 0\\. (precision p means p decimal digits.) the program and the analysis are valid for all p > 0, but current implementations place some restrictions on p.  t. e. hull a. abrham
algorithm 646: pdfind: a routine to find a positive definite linear combination of two real symmetric matrices  pdfind is a fortran-77 implementation of an algorithm that finds a positive definite linear combination of two symmetric matrices, or determines that such a combination does not exist. the algorithm is designed to be independent of the data structures used to store the matrices. the user must provide a subroutine, chlsky, which acts as an interface between pdfind and the matrix data structures. chlsky also provides the user control over the number of iterations of the algorithm. implementations of chlsky are included which call linpac routines for full matrices as well as symmetric banded matrices.  charles r. crawford
some tests of generalized bisection  this paper addresses the task of reliably finding approximations to all solutions to a system of nonlinear equations within a region defined by bounds on each of the individual coordinates. various forms of generalized bisection were proposed some time ago for this task. this paper systematically compares such generalized bisection algorithms to themselves, to continuation methods, and to hybrid steepest descent/quasi-newton methods. a specific algorithm containing novel "expansion" and "exclusion" steps is fully described, and the effectiveness of these steps is evaluated. a test problem consisting of a small, high-degree polynomial system that is appropriate for generalized bisection, but very difficult for continuation methods, is presented. this problem forms part of a set of 17 test problems from published literature on the methods being compared; this test set is fully described here.  r. baker kearfott
superconcentrators, generalizers and generalized connectors with limited depth  we show that the minimum possible size of an n-superconcentrator with depth 2k≥4 is (nλ(k, n)), where λ(k, .) is the inverse of a certain function at the k-th level of the primitive recursive hierarchy. it follows that the minimum possible depth of an n-superconcentrator with linear size is (β(n)), where β is the inverse of a function growing more rapidly than any primitive recursive function. similar results hold for generalizers.  we give a simple explicit construction for a (d1...d< ;subscrpt>k)-generalizer with depth k and size (d1+...+dk)d1...dk. this is applied to give a simple explicit construction for a generalized n-connector with depth 2k 3 and size (2d1+3d2& lt;/subscrpt>+...+3dk 1+2dk) d1...dk. these are the best explicit constructions currently available. we also show that, for each fixed k≥2, the minimum possible size of a generalized n-connector with depth k is Ω(n1+1/k) and 0((n log n)1+1/k).  danny dolev cynthia dwork nicholas pippenger avi wigderson
algorithm 652: hompack: a suite of codes for globally convergent homotopy algorithms  there are algorithms for finding zeros or fixed points of nonlinear systems of equations that are globally convergent for almost all starting points, i.e., with probability one. the essence of all such algorithms is the construction of an appropriate homotopy map and then tracking some smooth curve in the zero set of this homotopy map. hompack provides three qualitatively different algorithms for tracking the homotopy zero curve: ordinary differential equation-based, normal flow, and augmented jacobian matrix. separate routines are also provided for dense and sparse jacobian matrices. a high-level driver is included for the special case of polynomial systems.  layne t. watson stephen c. billups alexander p. morgan
finding boundaries of the domain of definition for functions along a one- dimensional ray  a program for finding boundaries of function domains along a one-dimensional ray has been developed. the program decomposes the function into subexpressions which are recursively tested for intervals where they are undefined, negative, or fractional, or points where they equal zero. the intervals in which the subexpressions are undefined are then united to create the boundaries of the domain of definition of the whole function. the advantages of the use of such a program in solution of systems of nonlinear algebraic equations and nonlinear optimization are demonstrated.  orit shacham mordechai schacham
multivariate interpolation of large sets of scattered data  this paper presents a method of constructing a smooth function of two or more variables that interpolates data values at arbitrarily distributed points. shepard's method for fitting a surface to data values at scattered points in the plane has the advantages of a small storage requirement and an easy generalization to more than two independent variables, but suffers from low accuracy and a high computational cost relative to some alternative methods. localizations of this method have reasonably low computational costs, but remain relatively inaccurate. we describe a modified shepard's method that, without sacrificing the advantages, has accuracy comparable to other local methods. computational efficiency is also improved by using a cell method for nearest-neighbor searching. test results for two and three independent variables are presented.  robert j. renka
a new approach to all pairs shortest paths in planar graphs  an algorithm is presented for generating a succinct encoding of all pairs shortest path information in a directed planar graph g with real-valued edge costs but no negative cycles. the algorithm runs in  (pn) time, where n is the number of vertices in g, and p is the minimum cardinality of a subset of the faces that cover all vertices, taken over all planar embeddings of g. linear- time algorithms are presented for various subproblems including that of finding an appropriate embedding of g and a corresponding face-on-vertex covering of cardinality  (p), and of generating all pairs shortest path information in a directed outerplanar graph.  g. n. frederickson
note on the end game in homotopy zero curve tracking  homotopy algorithms to solve a nonlinear system of equations f(x) = 0 involve tracking the zero curve of a homotopy map p(a, λ, x) from λ = 0 until λ = 1. when the algorithm nears or crosses the hyperplane λ = 1, an "end game" phase is begun to compute the solution x  satisfying p(a, λ, x ) = f(x ) = 0. this note compares several end game strategies, including the one implemented in the normal flow code fixpnf in the homotopy software package hompack.  maria sosonkina layne t. watson david e. stewart
parallel algorithms for minimum cuts and maximum flows in planar networks  algorithms are given that compute maximum flows in planar directed networks either in o((log n)3) parallel time using o(n4) processors or o((log n)2) parallel time using o(n6) processors. the resource consumption of these algorithms is dominated by the cost of finding the value of a maximum flow. when such a value is given, or when the computation is on an undirected network, the bound is o((log n)2) time using o(n3 ) processors. no efficient parallel algorithm is known for the maximum flow problem in general networks.  donald b. johnson
generating random variates from a distribution of phase type  an algorithm for generating phase type random variates is presented. a phase type distribution is any distribution which may be that of the time until absorption in a finite state markov process. the exponential sojourn times allow us to record only the number of visits, k, to each state before absorption and then generate appropriate erlang-k random variates. a related algorithm for the superposition of renewal processes of phase type is also discussed.  marcel f. neuts miriam e. pagano
deterministic distributed resource discovery (brief announcement)  the resource discovery problem was introduced by harchol-balter, leighton and lewin in [hll99], as a part of their work on web caching. they developed a randomized algorithm for the problem in the weakly connected directed graph model, that was implemented within lcs at mit, and then licensed to akamai technologies.  the directed graph is a logical one (as opposed to the underlying communication graph). it represents the nodes' "knowledge" about the topology of the underlying communication network. in [hll99] the notion of topology "knowledge" is simplified, by modeling it as a "knowledge" of an id of another node. in the general case such a "knowledge" may a include whole route, as well as any additional information needed in order to establish a connection (e.g. a cryptographic public key).  it is assumed (here, and in [hll99]) that the logical graph g is weakly connected. this can result from topology changes: e.g., a loss of a connection to a name server, or a gain of new knowledge that is uneven between different nodes, since it is obtained by distributed algorithms, and in non-homogeneous network.  note that weak connectivity is a necessary condition for the solvability of the problem. dealing efficiently with the weakly connected graph was, in fact, the main contribution in [hll99]. the alternative of transforming the graph into an undirected one, and then solving the problem on the resulting undirected graph, is possible. if e0 = o(n) it even leads to efficient solutions: a time optimal algorithm (for undirected graphs) appears in [sv82], it was designed for crcw pram, but can be translated into the model of [hll99] using oe0| log n) messages. the assumption that |e0| = o(n) may be suitable if topology changes are assumed to be limited. many practical distributed systems, however, attempt to deal with the case that the network may be partitioned. thus, e0 should be as big as possible, to enable the disconnected components to regain connectivity.  the current paper proposes a deterministic algorithm for the problem in the same model as that of [hll99]. our algorithm is near optimal in all the measures: time, message, and communication complexities. each previous algorithm had a complexity that was higher at least in one of the measures. specifically, previous deterministic solutions required either time linear in the diameter of the initial network, or communication complexity  ;o(n3) (with message complexity o(n& lt;/italic>2)), or message complexity < italic>o(|e0< ;/subscrpt>| log n) (where e0 is the edge set of the initial graph). compared to the main randomized algorithm of the harchol-balter, leighton, and lewin, the time complexity is reduced from _o(log2n ) to o(log n log* n), the message complexity from o(n log 2n) to o(n log n log * n), and the communication complexity from o(n2 log3 n) to o(|0|log2< /supscrpt> n \\+ n2 log n).  shay kutten david peleg
a multi-level solution algorithm for steady-state markov chains  a new iterative algorithm, the multi-level algorithm, for the numerical solution of steady state markov chains is presented. the method utilizes a set of recursively coarsened representations of the original system to achieve accelerated convergence. it is motivated by multigrid methods, which are widely used for fast solution of partial differential equations. initial results of numerical experiments are reported, showing significant reductions in computation time, often an order of magnitude or more, relative to the gauss-seidel and optimal sor algorithms for a variety of test problems. it is shown how the well-known iterative aggregation- disaggregation algorithm of takahashi can be interpreted as a special case of the new method.  graham horton scott t. leutenegger
algorithm 665: machar: a subroutine to dynamically determined machine parameters  numerical software written in high-level languages often relies on machine- dependent parameters to improve portability. machar is an evolving fortran subroutine for dynamically determining thirteen fundamental parameters associated with a floating-point arithmetic system. the version presented here operates correctly on a large number of different floating- point systems, including those implementing the new ieee floating-point standard.  w. j. cody
computer implementation of multiple comparisons with the best and selection procedures  the lack of computer software for ranking and selection has often been cited as a reason for it not having caught on in practice (hayes 1982). actually, this lack of software was a manifestation of some deeper perceived difficulties with practical usage, we believe. it was perceived that bechhofer's (1954) indifference zone selection type inference was unavailable for single-stage experiments. the multiple comparisons with the best (mcb) result of hsu (1981) showed that not only is it available for single-stage experiments, it can be given simultaneously with gupta's (1965) subset selection inference without decreasing the minimum confidence level of either. it has also been perceived that the unequal sample size case requires more complex methodologies than the equal sample size case. it is pointed out in hsu (1983) that, so long as the analysis is performed on the computer, there needs to be no difference in methodology between the two cases. based on these recent developments, a computer package has been written for multiple comparisons with the best. given the data (equal sample size or not) and the desired confidence level p* ( 1 α), the first page output includes subset selection inference and indifference zone selection inference (extended to single-stage experiments), while the second page output gives the confidence intervals inference of hsu (1981, 1982). all the inferences are guaranteed to be correct simultaneously with a probability of at least p*. the result of analysis of some water filter data using an earlier version of the package has been reported in lorenz, hsu, and tuovinen (1982).  jason c. hsu
evaluation of step directions in optimization algorithms  we present a method for comparing that part of optimization algorithms that chooses each step direction. it is an example of a general approach to algorithm evaluation in which one tests specific parts of the algorithm, rather than making overall evaluations on a set of standard test problems. our testing procedure can he useful for developing new algorithms and for writing and evaluating optimization software.  we use the method to compare two versions of the conjugate gradient algorithm, and to compare these with an algorithm based on conic functions.  william c. davidon jorge nocedal
on monotone paths among obstacles with applications to planning assemblies  we study the class of problems associated with the detection and computation of monotone paths among a set of disjoint obstacles. we give an  (ne) algorithm for finding a monotone path (if one exists) between two points in the plane in the presence of polygonal obstacles. (here, e is the size of the visibility graph defined by the n vertices of the obstacles.) if all of the obstacles are convex, we prove that there always exists a monotone path between any two points s and t. we give an  (n log n) algorithm for finding such a path for any s and t, after an initial  (e \\+ n log n) preprocesing. we introduce the notions of "monotone path map", and "shortest monotone path map" and give algorithms to compute them. we apply our results to a class of separation and assembly problems, yielding polynomial-time algorithms for planning an assembly sequence (based on separations by single translations) of arbitrary polygonal parts in two dimensions.  e. m. arkin r. connelly j. s. mitchell
rejection-inversion to generate variates from monotone discrete distributions  for discrete distributions a variant of reject from a continuous hat function is presented. the main advantage of the new method, called rejection- inversion, is that no extra uniform random number to decide between acceptance and rejection is required, which means that the expected number of uniform variates required is halved. using rejection-inversion and a squeeze, a simple universal method for a large class of monotone discrete distributions is developed. it can be used to generate variates from the tails of most standard discrete distributions. rejection- inversion applied to the zipf (or zeta) distribution results in algorithms that are short and simple and at least twice as fast as the fastest methods suggested in the literature.  w. hörmann g. derflinger
interactive ellpack: an interactive problem-solving environment for elliptic partial differential equations  ellpack is a versatile, very high- level language for solving elliptic partial differential equations.solving elliptic problems with ellpack typically involves a process in which one repeatedlycomputes a solution, analyzes the results, and modifies the solution technique. although this processis best suited for an interactive environment, ellpack itself is batch oriented. with this in mind,we have developed interactive ellpack, an extension of ellpack that provides true interactiveelliptic problem solving by allowing the user to interactively build grids, choose solution methods,and analyze computed results. interactive ellpack features a sophisticated interface with window- ing, color graphics output, and graphics input.  wayne r. dyksen calvin j. ribbens