waashk/acm huggingface dataset:
n-processors graphs distributively achieve perfect matchings in o(log2n) beats  a perfect matching in a graph g(v,e), also called a 1-factor, is a collection p of non-interesting edges engaging (incident with) all the vertices; in case g is bipartite v m @@@@ f, m @@@@ f , p should engage all the vertices of m. the combinatorial problem of finding a perfect matching in g (and its rich ramifications) were extensively studied (and applied) from existential, algorithmic and probabilistic points of view.  here we replace sequential algorithms by distributive, parallel ones. we imagine n processors without a shared memory or a central coordinator (except a clock) reside at the n vertices and communicate by messages. for each particular problem, the edges (giving direct connections) are given and define the input graph g. the collectin of all these graphs is made into a probability space gn (in several ways, as explicated below). in one synchronized step ( beat), each processor can send a message to a neighbor along an edge of g. one can cheaply implement such steps, uniformly for all graphs, with an efficient switchboard.  eli shamir eli upfal
a symbolic computation method of analytic solution of the mixed direchlet- neumann-robin problem for laplace's equation  the authors show how to use symbolic computing methods to obtain an analytic representation of the solution of  laplace's equation (in r2 or r3) satisfying boundary conditions of a very general type, viz., involving conditions of dirichlet, neumann and robin's type on disjoint subsets of the boundary of the solution domain.  herbert h. snyder ralph w. wilkerson
sparse matrix test problems  we describe the harwell-boeing sparse matrix collection, a set of standard test matrices for sparse matrix problems. our test set comprises problems in linear systems, least squares, and eigenvalue calculations from a wide variety of scientific and engineering disciplines. the problems range from small matrices, used as counter-examples to hypotheses in sparse matrix research, to large test cases arising in large- scale computation. we offer the collection to other researchers as a standard benchmark for comparative studies of algorithms. the procedures for obtaining and using the test collection are discussed. we also describe the guidelines for contributing further test problems to the collection.  i. s. duff roger g. grimes john g. lewis
algorithm 691; improving quadpack automatic integration routines  two automatic adaptive integrators from quadpack (namely, qag, and qags) are modified by substituting the gauss-kronrod rules used for local quadrature with recursive monotone stable (rms) formulas. extensive numerical tests, both for one-dimensional and two-dimensional integrals, show that the resulting programs are faster, perform less functional evaluations, and are more suitable  paola favati grazia lotti francesco romani
towards efficient implementation of singly-implicit methods  it has been observed that for problems of low dimension the transformations used in the implementation of singly-implicit runge-kutta methods consume an unreasonable share of the total computational costs. two proposals for reducing these costs are presented here. the first makes use of an alternative transformation for which the combined operation counts of the transformations together with the iterations themselves are lower than for the standard implementation scheme for singly-implicit methods. the second proposal is to use a runge-kutta method for which the first row of the coefficient matrix is zero but which still possesses acceptable stability properties. it is hoped that by combining these two proposals increased efficiency in the implementation of runge-kutta methods for stiff problems can be achieved.  j. c. butcher
the electrical resistance of a graph captures its commute and cover times  view an n-vertex, m-edge undirected graph as an electrical network with unit resistors as edges. we extend known relations between random walks and electrical networks by showing that resistance in this network is intimately connected with the lengths of random walks on the graph. for example, the commute time between two vertices s and t (the expected length of a random walk from s to t and back) is precisely characterized by the effective resistance rst between s and t: commute time = 2mrst. additionally, the cover time (the expected length of a random walk visiting all vertices) is characterized by the maximum resistance r in the graph to within a factor of log n: mr ≤ cover time ≤ o (mr log n). for many graphs, the bounds on cover time obtained in this manner are better than those obtained from previous techniques such as the eigenvalues of the adjacency matrix. in particular, using this approach, we improve known bounds on cover times for various classes of graphs, including high-degree graphs, expanders, and multi- dimensional meshes. moreover, resistance seems to provide an intuitively appealing and tractable approach to these problems.  a. k. chandra p. raghavan w. l. ruzzo r. smolensky
necessary and sufficient conditions for hyperplane transversals  we will prove that a finite family b = {b1, b2, …, bn} of connected compact sets in rd has a hyperplane transversal if and only if for some k there exists a set of points p = {p1, p2, …, pn} (i.e. a k-dimensional labeling of the family) which spans rk and every k \\+ 2 sets of b are met by a k-flat consistent with the order type of p. this is a common generalization of theorems of hadwiger, katchalski, goodman-pollack and wenger.  r. pollack r. wenger
queueing delays on virtual circuits using a sliding window flow control scheme  a tandem queue model is developed that models the end-to-end delay behavior in networks that employ sliding window flow control. messages arriving to find the window filled are assumed to be queued outside the network to await their turn to enter. the model is analyzed using a hierarchical decomposition method; the key step entails incorporating the fact that the interdeparture process is not exponentially distributed. end-to-end delay in virtual circuits can then be obtained by modelling a virtual route as a tandem queue [1] using the method of "adjusted rates."  g. varghese w. chou a. a. nilsson
reservoir-sampling algorithms of time complexity o(n(1 + log(n/n)))  one-pass algorithms for sampling n records without replacement from a population of unknown size n are known as reservoir-sampling algorithms. in this article, vitter's reservoir-sampling algorithm, algorithm z, is modified to give a more efficient algorithm, algorithm k. additionally, two new algorithms, algorithm l and algorithm m, are proposed. if the time for scanning the population is ignored, all the four algorithms have expected cpu time o(n(1 + log(n/n))), which is optimum up to a constant factor. expressions of the expected cpu time for the algorithms are presented. among the four, algorithm l is the simplest, and algorithm m is the most efficient when n and n/n are large and n is o( ;n2).  kim-hung li
an interface optimization and application for the numerical solution of optimal control problems  an interface between the application problem and the nonlinear optimization algorithm is proposed for the numerical solution of distributed optimal control problems. by using this interface, numerical optimization algorithms can be designed to take advantage of inherent problem features like the splitting of the variables into states and controls and the scaling inherited from the functional scalar products. further, the interface allows the optimization algorithm to make efficient use of user-provided function evaluations and derivative calculations.  matthias heinkenschloss luís n. vicente
accurate approximate solution of partial differential equations at off-mesh points  numerical methods for partial differential equations often determine approximations that are more accurate at the set of discrete meshpoints than they are at the "off-mesh" points in the domain of interest. these methods are generally most effective if they are allowed to adjust the location of the mesh points to match the local behavior of the solution. different methods will typically generate their respective approximations on incompatible, unstructured meshes, and it can be difficult to evaluate the quality of a particular solution, or to visualize important properties of a solution. in this paper we will introduce a generic approach which can be used to generate approximate solution values at arbitrary points in the domain of interest for any method that determines approximations to the solution and low-order derivatives at meshpoints. this approach is based on associating a set of "collocation" points with each mesh element and requiring that the local approximation interpolate the meshpoint data and almost satisfy the partial differential equation at the collocation points. the accuracy associated with this interpolation/collocation approach is consistent with the "meshpoint accuracy" of the underlying method. the approach that we develop applies to a large class of methods and problems. it uses local information only and is therefore particularly suitable for implementation in a parallel or network computing environment. numerical examples are given for some second-order problems in two and three dimensions.  w. h. enright
calculating equilibrium probabilities for (n)/ck/1/n queues  equilibrium state distributions are determined for queues with load-dependent poisson arrivals and service time distributions representable by cox's generalized method of stages. the solution is obtained by identifying a birth- death process that has the same equilibrium state distribution as the original queue. special cases of two-stage (c2) and erlang-k (ek) service processes permit particularly efficient algorithms for calculating the load - dependent service rates of the birth-death process corresponding to the original queue. knowing the parameters of the birth-death process, the equilibrium state probabilities can be calculated straight-forwardly. this technique is particularly useful when subsystems are reduced to flow-equivalent servers representing the complementary network.  raymond marie
solving minimum-cost flow problems by successive approximation  we introduce a framework for solving minimum-cost flow problems. our approach measures the quality of a solution by the amount that the complementary slackness conditions are violated. we show how to extend techniques developed for the maximum flow problem to improve the quality of a solution. this framework allows us to achieve  (min(3, n5/3 m2/3, nm log n) log (nc)) running time.  a. goldberg r. tarjan
iterative aggregation/disaggregation techniques for nearly uncoupled markov chains  iterative aggregation/disaggregation methods provide an efficient approach for computing the stationary probability vector of nearly uncoupled (also known as nearly completely decomposable) markov chains. three such methods that have appeared in the literature recently are considered and their similarities and differences are outlined. specifically, it is shown that the method of takahashi corresponds to a modified block gauss-seidel step and aggregation, whereas that of vantilborgh corresponds to a modified block jacobi step and aggregation. the third method, that of koury et al., is equivalent to a standard block gauss-seidel step and iteration. for each of these methods, a lemma is established, which shows that the unique fixed point of the iterative scheme is the left eigenvector corresponding to the dominant unit eigenvalue of the stochastic transition probability matrix. in addition, conditions are established for the convergence of the first two of these methods; convergence conditions for the third having already been established by stewart et al. all three methods are shown to have the same asymptotic rate of convergence.  wei-lu cao william j. stewart
a comparison of adaptive refinement techniques for elliptic problems  adaptive refinement has proved to be a useful tool for reducing the size of the linear system of equations obtained by discretizing partial differential equations. we consider techniques for the adaptive refinement of triangulations used with the finite element method with piecewise linear functions. several such techniques that differ mainly in the method for dividing triangles and the method for indicating which triangles have the largest error have been developed. we describe four methods for dividing triangles and eight methods for indicating errors. angle bounds for the triangle division methods are compared. all combinations of triangle divisions and error indicators are compared in a numerical experiment using a population of eight test problems with a variety of difficulties (peaks, boundary layers, singularities, etc.). the comparison is based on the l-infinity norm of the error versus the number of vertices. it is found that all of the methods produce asymptotically optimal grids and that the number of vertices needed for a given error rarely differs by more than a factor of two.  william f. mitchell
algorithms column this column will discuss recent developments in the field of algorithms. i expect that the results reported here will be from recent conferences or workships. this column could be useful to the reader who may not keep track of new developments in the field of algorithms. guest columns on special topics will be welcomed. two problems that have recieved a lot of attention during the last few years are the problems of facility location and the related problem of _k_-medians. i will describe the problems, provide a brief summary of prior work, and then describe one of the main results from a paper [1] to apprear at stoc 2001 to be held in crete, greece. samir khuller
a recursive formulation of cholesky factorization of a matrix in packed storage  a new compact way to store a symmetric or triangular matrix called rpf for recursive packed format is fully described. novel ways to transform rpf to and from standard packed format are included. a new algorithm, called rpc for recursive packed cholesky, that operates on the rpg format is presented. algorithm rpc is basd on level-3 blas and requires variants of algorithms trsm and syrk that work on rpf. we call these rp_trsm and rp_syrk and find that they do most of their work by calling gemm. it follows that most of the execution time of rpc lies in gemm. the advantage of this storage scheme compared to traditional packed and full storage is demonstrated. first, the rpc storage format uses the minimal amount of storage for the symmetric or triangular matrix. second, rpc gives a level-3 implementation of cholesky factorization whereas standard packed implementations are only level 2. hence, the performance of our rpc implementation is decidedly superior. third, unlike fixed block size algorithms, rpc, requires no block size tuning parameter. we present performance measurements on several current architectures that demonstrate improvements over the traditional packed routines. also msp parallel computations on the ibm smp computer are made. the graphs that are attached in section 7 show that the rpc algorithms are superior by a factor between 1.6 and 7.4 for order around 1000, and between 1.9 and 10.3 for order around 3000 over the traditional packed algorithms. for some architectures, the rpc performance results are almost the same or even better than the traditional full-storage algorithms results.
beware of linear congruential generators with multipliers of the form a = ±2q ±2r  linear congruential random-number generators with mersenne prime modulus and multipliers of the form a = ±2q ±r have been proposed recently. their main advantage is the availability of a simple and fast implementation algorithm for such multipliers. this note generalizes this algorithm, points out statistical weaknesses of these multipliers when used in a straightforward manner, and suggests in what context they could be used safely.  pierre l'ecuyer richard simard
portable vectorized software for bessel function evaluation  a suite of computer programs for the evaluation of bessel functions and modified bessel functions of orders zero and one for a vector of real arguments is described. distinguishing characteristics of these programs are that (a) they are portable across a wide range of machines, and (b) they are vectorized in the case when multiple function evaluations are to be performed. the performance of the new programs are compared with software from the fnlib collection of fullerton on which the new software is based.  ronald f. boisvert bonita v. saunders
a frontal code for the solution of sparse positive-definite symmetric systems arising from finite-element applications  we describe the design, implementation, and performance of a frontal code for the solution of large sparse symmetric systems of linear finite-element equations. the code is intended primarily for positive-definite systems, since numerical pivoting is not performed. the resulting software package, ma62, will be included in the harwell subroutine library. we illustrate the performance of our new code on a range of problems arising from real engineering and industrial applications. the performance of the code is compared with that of the harwell subroutine library general frontal solver ma42 and with other positive-definite codes from the harwell subroutine library.  iain s. duff jennifer a. scott
modularity of cycles and paths in graphs  certain problems related to the length of cycles and paths modulo a given integer are studied. linear-time algorithms are presented that determine whether all cycles in an undirected graph are of length p mod q and whether all paths between two specified nodes are of length p mod q, for fixed integers p.q. these results are compared to those for directed graphs.  e. m. arkin c. h. papadimitriou m. yannakakis
hypercube implementation of the simplex algorithm  large, sparse, linear systems of equations arise frequently when constructing mathematical models of natural phenomena. most often, these linear systems are fully constrained and can be solved via direct or iterative techniques. however, one important problem class requires solutions to underconstrained linear systems that maximize some objective function. these linear optimization problems are natural formulations of many business plans and often contain hundreds of equations with thousands of variables. historically, linear optimization problems have been solved via the simplex method. despite the excellent performance of the simplex method, the size of the optimization problems and the frequency of their solution make linear optimization a computationally taxing endeavor. this paper examines the performance of parallel variants of the simplex algorithm on the intel ipsc, a message-based parallel system. linear optimization test data are drawn from commercial sources and represent realistic problems. analysis shows that the speedup obtained is sensitive to both the structure of the underlying data and the data partitioning.  c. b. stunkel d. a. reed
bounds on threshold dimension and disjoint threshold coverings (abstract only)  the threshold dimension1 of a graph g is the smallest number of threshold graphs needed to cover the edges of g. if t(n) is the greatest threshold dimension of any graph of n vertices, we show that for some constant c, n-c n log n < t(n) < n- n + 1 we establish the same bounds for edge-disjoint coverings of graphs by threshold graphs. the results have applications to manipulating systems of simultaneous linear inequalities and to space bounds for synchronization problems2.  p. erdos e. ordman y. zalcstein
algorithm 655: iqpack: fortran subroutines for the weights of interpolatory quadratures  we present fortran subroutines that implement the method described in [3] for the stable evaluation of the weights of interpolatory quadratures with prescribed simple or multiple knots. given a set of knots and their multiplicities, the package generates the weights by using the zeroth moment μ0 of w, the weight function in the integrand, and the (symmetric tridiagonal) jacobi matrix j associated with the polynomials orthogonal on (a, b) with respect to w. there are utility routines that generate μ0 and j for classical weight functions, but quadratures can be generated for any μ0 and j supplied by the user. utility routines are also provided that (1) evaluate a computed quadrature, applied to a user-supplied integrand, (2) check the polynomial order of precision of a quadrature formula, and (3) compute the knots and weights of simple gaussian quadrature formula.  sylvan elhay jaroslav kautsky
algorithm 656: an extended set of basic linear algebra subprograms: model implementation and test programs  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.  jack j. dongarra jeremy du croz sven hammarling richard j. hanson
on computing a separating transcendence basis let _k_(1,…, _xn_)/_k_ be a finitely generated field extension, and _g_1_,…,_gr_ ε _k_(x). for _k_(_x_,…,_xn_)/&amp;l; t;i>k_(_g_1,…,& lt;i>gr_) being separably generated (which in particular includes the case char(_k_) = 0) we give a method to compute the transcendence degree and a separating transcendence basis of this extension by means of simple linear algebra techniques. rainer steinwandt
algorithm 716; tspack: tension spline curve-fitting package  the primary purpose of tspack is to construct a smooth function which interpolates a discrete set of data points. the function may be required to have either one or two continuous derivatives. if the accuracy of the data does not warrant interpolation, a smoothing function (which does not pass through the data points) may be constructed instead. the fitting method is designed to avoid extraneous inflection points (associated with rapidly varying data values) and preserve local shape properties of the data (monotonicity and convexity), or to satisfy the more general constraints of bounds on function values or first derivatives. the package also provides a parametric representation for construction general planar curves and space curves.  r. j. renka
multicolor reordering of sparse matrices resulting from irregular grids  many iterative algorithms for the solution of large linear systems may be effectively vectorized if the diagonal of the matrix is surrounded by a large band of zeroes, whose width is called the zero stretch. in this paper, a multicolor numbering technique is suggested for maximizing the zero stretch of irregularly sparse matrices. the technique, which is a generalization of a known multicoloring algorithm for regularly sparse matrices, executes in linear time, and produces a zero stretch approximately equal to n/2 , where 2 is the number of colors used in the algorithm. for triangular meshes, it is shown that ≤ 3, and that it is possible to obtain = 2 by applying a simple backtracking scheme.  rami g. melhem k. v. s. ramarao