waashk/acm huggingface dataset:
on threshold pivoting in the multifrontal method for sparse indefinite systems  a simple modification to the numerical pivot selection criteria in the multifrontal scheme of duff and reid for sparse symmetric matrix factorization is presented. for a given threshold value, the modification allows a broader choice of block 2 x 2 pivots owing to a less restrictive pivoting condition. it also extends the range of permissible threshold values from [0, 1/2) to [0, 0.6404). moreover, the bound on element growth for stability consideration in the modified scheme is nearly the same as that of the original strategy.  joseph w. h. liu
modification of the minimum-degree algorithm by multiple elimination  the most widely used ordering scheme to reduce fills and operations in sparse matrix computation is the minimum-degree algorithm. the notion of multiple elimination is introduced here as a modification to the conventional scheme. the motivation is discussed using the k-by-k grid model problem. experimental results indicate that the modified version retains the fill-reducing property of (and is often better than) the original ordering algorithm and yet requires less computer time. the reduction in ordering time is problem dependent, and for some problems the modified algorithm can run a few times faster than existing implementations of the minimum-degree algorithm. the use of external degree in the algorithm is also introduced.  joseph w. h. liu
algorithm 726; orthpol - a package of routines for generating orthogonal polynomials and gauss-type quadrature rules  a collection of subroutines and examples of their uses, as well as the underlying numerical methods, are described for generating orthogonal polynomials relative to arbitrary weight functions. the object of these routines is to produce the coefficients in the three-term recurrence relation satisfied by the orthogonal polynomials. once these are known, additional data can be generated, such as zeros of orthogonal polynomials and gauss-type quadrature rules, for which routines are also provided.  walter gautschi
on ordered languages and the optimization of linear functions by greedy algorithms  the optimization problem for linear functions on finite languages is studied, and an (almost) complete characterization of those functions for which a primal and a dual greedy algorithm work well with respect to a canonically associated linear programming problem is given. the discussion in this paper is within the framework of ordered languages, and the characterization uses the notion of rank feasibility of a weighting with respect to an ordered language. this yields a common generalization of a sufficient condition, obtained recently by korte and lovasz for greedoids, and the greedy algorithm for ordered sets in faigel's paper [6]. ordered greedoids are considered the appropriate generalization of greedoids, and the connection is established between ordered languages, polygreedoids, and coxeteroids. answering a question of bjorner, the author shows in particular that a polygreedoid is a coxeteroid if and only if it is derived from an integral polymatroid.  ulrich faigle
finding minimum-cost circulations by canceling negative cycles  a classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an arc. we show that a judicious choice of cycles for canceling leads to a polynomial bound on the number of iterations in this algorithm. this gives a very simple strongly polynomial algorithm that uses no scaling. a variant of the algorithm that uses dynamic trees runs in (nm(log n)min{log(nc), m log n}) time on a network of n vertices, m arcs, and arc costs of maximum absolute value c. this bound is comparable to those of the fastest previously known algorithms.  andrew v. goldberg robert e. tarjan
efficient algorithms for inverting evolution  evolution can be mathematically modelled by a stochastic process that operates on the dna of species. such models are based on the established theory that the dna sequences, or genomes, of all extant species have been derived from the genome of the common ancestor of all species by a process of random mutation and natural selection.  a stochastic model of evolution can be used to construct phylogenies, or evolutionary trees, for a set of species. maximum likelihood estimation (mle) methods seek the evolutionary tree which is most likely to have produced the dna under consideration. while these methods are intellectually satisfying, they have not been widely accepted because of their computational intractability.  in this paper, we address the intractability of mle methods as follows: we introduce a metric on stochastic process models of evolution. we show that this metric is meaningful by proving that in order for any algorithm to distinguish between two stochastic models that are close according to this metric, it needs to be given many observations. we complement this result with a simple and efficient algorithm for inverting the stochastic process of evolution, that is, for building a tree from observations on two-state characters. (we will use the same techniques in a subsequent paper to solve the problem for multistate characters, and hence for building a tree from dna sequence data.) the tree we build is provably close, in our metric, to the tree generating the data and gets closer as more observations become available.  though there have been many heuristics suggested for the problem of finding good approximations to the most likely tree, our algorithm is the first one with a guaranteed convergence rate, and further, this rate is within a polynomial of the lower-bound rate we establish. ours is also the first polynomial-time algorithm that is proven to converge at all to the correct tree.  martin farach sampath kannan
vectorized dissection on the hypercube  dissection ordering is used with gaussian elimination on a hypercube parallel processor with vector hardware to solve matrices arising from finite- difference and finite-element discretizations of 2-d elliptic partial differential equations. these problems can be put into a matrix-vector form, ax = f, where the matrix a takes the place of the differential operator, x is the solution vector, and f is the source vector. the domain is divided among the nodes with neighboring subdomains sharing a strip called a separator. each processor is given its own part of the source vector and computes its own part of the stiffness matrix, a.  the elimination starts out in parallel; communication is only needed after most of the elimination is finished when the edges need to be eliminated. back substitution is initially done on the domain edges, and then totally in parallel without communication on each node. the hypercube code involved was optimized to work with vector hardware. example problems and timings are given with comparisons to nonvector runs.  t-h. olesen j. petersen
incremental modular decomposition  modular decomposition is a form of graph decomposition that has been discovered independently by researchers in graph theory, game theory, network theory, and other areas. this paper reduces the time needed to find the modular decomposition of a graph from (n3) to (n2). together with a new algorithm for transitive orientation given in [21], this leads to fast new algorithms for a number of problems in graph recognition and isomorphism, including recognition of comparability graphs and permutation graphs. the new algorithm works by inserting each vertex successively into the decomposition tree, using (n) time to insert each vertex.  john h. muller jeremy spinrad
computation of exponential integrals of a complex argument  previous work on exponential integrals of a real argument has produced a computational algorithm which implements backward recurrence on a three-term recurrence relation (miller algorithm). the process on which the algorithm is based involves the truncation of an infinite sequence with a corresponding analysis of the truncation error. this error is estimated by means of (asymptotic) formulas, which are not only applicable to the real line, but also extendible to the complex plane. this fact makes the algorithm extendible to the complex plane also. however, the rate of convergence decreases sharply when the complex argument is close to the negative real axis. in order to make the algorithm more efficient, analytic continuation into a strip about the negative real axis is carried out by limited use of power series. the analytic details needed for a portable computational algorithm are presented.  donald e. amos
transient diffusion approximation for some queuening systems.  there are many situations where information about the transient behaviour of computer systems is wanted. in this paper a diffusion approximation to the transient behaviour of some queueing systems is proposed. the solution of the forward diffusion equation on the real positive line with the elementary return barrier having almost general holding time distribution provides the approximation for the gi/g/1 queue. the solution of the diffusion equation in a finite region approximates the transient behaviour for the two-server cyclic system and gives approximations for the first overflow time in the gi/g/1/n system and for the maximum number of customers in the gi/g/1 system. also the approximation for the busy period of the gi/g/1 system and of the two-server cyclic system are presented.  andrzej duda
radix-b extensions to some common empirical tests for pseudorandom number generators  empirical testing of computer generated pseudo-random sequences is widely practiced. extensions to the coupon collector's and gap tests are presented that examine the distribution and independence of radix-b digit patterns in sequences with modulo of the form bw. an algorithm is given and the test is applied to a number of popular generators. theoretical expected values are derived for a number of defects that may be present in a pseudorandom sequence and additional empirical evidence is given to support these values. the test has a simple model and a known distribution function. it is easily and efficiently implemented and easily adaptable to testing only the bits of interest, griven a certain application.  brad c. johnson
investigating des with crack and related programs the aim of the package to be described is to try modularizing the investigation of differential equations for which there are no complete algorithms available yet. all, that is available for such problems are algorithms for special situations, e.g. when first integrals with a simple structure exist (e.g. polynomial in first derivatives) or when the problem has infinitesimal symmetries. in all such cases, finally a system of differential equations has to be solved which is overdetermined in the sense that more conditions have to be satisfied than there are unknown functions. to do a variety of such investigations efficiently, like a symmetry analysis, application of symmetries, determination of first integrals, differential factors, equivalent lagrangians, the strategy is to have one package (crack) for simplifying des and solving simple des as effective as possible and to use this program as the main tool for all the above mentioned investigations. for each investigation there is then only a short program necessary to just formulate the necessary conditions in form of an overdetermined de-system and to call crack to solve this, possibly in a number of successive calls. the examples below shall indicate the range of possible applications. thomas wolf andreas brand
lower bounds for solving linear diophantine equations on random access machines  the problem of recognizing the language l~~n(ln, k) of solvable diophantine linear equations with n variables (and solutions from {o, … , k}n&amp;l; t;/supscrpt>) is considered. the languages ∪nεn ln, ∪& lt;italic>nεn ln, l, the knapsack problem, are np-complete. the (n2 lower bound for ln,1 on linear search algorithms due to dobkin and lipton is generalized to an (n2log(k& lt;/italic> \\+ 1)) lower bound for ln, k. the method of klein and meyer auf der heide is further improved to carry over the (n2) lower bound for ln, 1 to random access machines (rams) in such a way that it holds for a large class of problems and for very small input sets. by this method, lower bounds that depend on the input size, as is necessary for ln, are proved. thereby, an (n2l og(k \\+ 1)) lower bound is obtained for rams recognizing ln or ln, k, for inputs from {0, … , (nk)& lt;supscrpt>0(n 2)}n.  friedhelm meyer auf der heide
fortran codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation  fortran 77 codes sonest and conest are presented for estimating the 1-norm ( or the infinity-norm) of a real or complex matrix, respectively. the codes are of wide applicability in condition estimation since explicit access to the matrix, a, is not required; instead, matrix-vector products ax and atx are computed by the calling program via a reverse communication interface. the algorithms are based on a convex optimization method for estimating the 1-norm of a real matrix devised by hager. we derive new results concerning the behavior of hager's method, extend it to complex matrices, and make several algorithmic modifications in order to improve the reliability and efficiency.  nicholas j. higham
algorithm 688; epdcol: a more efficient pdecol code  the software package pdecol [7] is a popular code among scientists wishing to solve systems of nonlinear partial differential equations. the code is based on a method-of- lines approach, with collocation in the space variable to reduce the problem to a system of ordinary differential equations. there are three principal components: the basis functions employed in the collocation; the method used to solve the system of ordinary differential equations; and the linear equation solver which handles the linear algebra. this paper will concentrate on the third component, and will report on the improvement in the performance of pdecol resulting from replacing the current linear algebra modules of the code by modules which take full advantage of the special structure of the equations which arise. savings of over 50 percent in total execution time can be realized.  p. keast p. h. muir
an o(n0.4this paper presents a polynomial-time algorithm to color any 3-colorable n-node graph with o( n2/5 log8/5 n) colors, improving the best previously known bound of o( n/ logn) colors. by reducing the number of colors needed to color a 3-colorable graph, the algorithm also improves the bound for k-coloring for fixed k ≥ 3 from the previous o((n/log )1-1/(k-1)< /supscrpt>) colors to o(n1-1/(k-4/3)8/5 n) colors. an extension of the algorithm further improves the bounds. precise values appear in a table at the end of this paper.  a. blum
planar graph decomposition and all pairs shortest paths  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 o(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. the algorithm is based on a decomposition of the graph into o(pn) outerplanar subgraphs satisfying certain separator properties. 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 o(p), and of generating all pairs shortest path information in a directed outerplannar graph.  greg n. frederickson
statistical techniques of timing verification  timing verification of vlsi designs using statistical techniques such as those implemented in hitchcock's timing analysis1 permit a far more precise assessment of machine performance than previous techniques. the accuracy of these results is affected by proper user specification of statistical input parameters and by the algorithmic treatment of the system design. since these items are both system and technology dependent, the system designer must understand them and apply appropriate statistical techniques in order to insure a properly verified design. this paper both outlines the mathematical derivations and illustrates the magnitude of the improvements to be obtained.  james h. shelly david r. tryon
algorithm 778: l-bfgs-b: fortran subroutines for large-scale bound-constrained optimization  l-bfgs-b is a limited-memory algorithm for solving large nonlinear optimization problems subject to simple bounds on the variables. it is intended for problems in which information on the hessian matrix is difficult to obtain, or for large dense problems. l-bfgs-b can also be used for unconstrained problems and in this case performs similarly to its predessor, algorithm l-bfgs (harwell routine va15). the algorithm is implemented in fortran 77.  ciyou zhu richard h. byrd peihuang lu jorge nocedal
on sparse matrix reordering for parallel factorization  to minimize the amount of computation and storage for parallel sparse factorization, sparse matrices have to be reordered prior to factorization. we show that none of the popular ordering heuristics proposed before, namely, mulitple minimum degree and nested dissection, perform consistently well over a range of matrices arising in diverse application domains. spectral partitioning has been previously proposed as a means of generating small vertex separators for nested dissection of sparse matrices, so that the resulting ordering is amenable to efficient distributed parallel factorization with good load balance and low inter-processor communication. we show that nested dissection using spectral partitioning performs well for matrices arising from finite- element discretizations, but results in excessive fill compared to the minimum degree ordering for unstructured matrices such as power matrices and those arising from circuit simulation. the relative effectiveness of these two ordering schemes for parallel factorization is shown to vary widely for matrices arising from different application domains. we present an ordering strategy that performs consistently well for all matrix types. its ordering is comparable or better than either minimum degree or nested dissection for all matrices evaluated. performance results on the intel ipsc/860 are reported.  b. kumar p. sadayappan c.-h. huang
an exact analysis of the distribution of cycle times in a class of queueing networks  prediction of detailed characteristics of the time delays experienced by customers in queueing networks is of great importance in various modelling and performance evaluation activities: operations research, computer systems and communication networks. their statistical properties have been investigated predominantly by simulation techniques with the exception of mean value analyses for which little's law is applied. theoretical studies of the probability distributions of time delays tend to be based on their laplace transforms, which are of limited use, can be inverted analytically only in very simple cases and present substantial computation problems for numerical inversion. an exact derivation is presented for the distribution of cycle times in so called tree-like queueing networks. the analysis is performed for a network structure which is such that it is not necessary to mark a special customer, so avoiding expansion of the state space. cycle time distribution is derived initially in the form of its laplace transform, from which its moments follow. a recurrence relation for a uniformly convergent discrete representation of the distribution then follows by a similar argument. finally, the numerical results obtained for some simple test networks are presented and compared with those corresponding to an approximate method, hence indicating the accuracy of the latter.  p g harrison
analysis of non-strict functional implementations of the dongarra-sorensen eigensolver  we study the producer-consumer parallelism of eigensolvers composed of a tridiagonalization function, a tridiagonal solver, and a matrix multiplication, written in the non-strict functional programming language id. we verify the claim that non-strict functional languages allow the natural exploitation of this type of parallelism, in the framework of realistic numerical codes. we compare the standard top-down dongarra-sorensen solver with a new, bottom-up version. we show that this bottom-up implementation is much more space efficient than the top-down version. also, we compare both versions of the dongarra-sorensen solver with the more traditional ql algorithm, and verify that the dongarra-sorensen solver is much more efficient, even when run in a serial mode. we show that in a non-strict functional execution model, the dongarra-sorensen algorithm can run completely in parallel with the householder function. moreover, this can be achieved without any change in the code components. we also indicate how the critical path of the complete eigensolver can be improved.  s. sur w. böhm
algorithm 743; wapr: a fortran routine for calculating real values of the w-function  we implement w-function approximation scheme described by barry et al. a range of tests of the approximations is included so that the code can be assessed on any given machine. users can calculate w(x) by specifying x itself or by specifying an offset from exp( 1), the latter option necessitated by rounding errors that can arise for x close to exp( 1). results of running the code on a sun workstation are included.  d. a. barry s. j. barry p. j. culligan- hensley
equilibrium states of runge-kutta schemes: part ii  a theory is given that accounts for the observed behavior of runge-kutta codes when the stepsize is restricted by stability. the theory deals with the general case when the dominant eigenvalues of the jacobian may be a complex conjugate pair. this extends and generalizes the results of part i of this paper, which deal with the real case. familiarity with part i is assumed, but not essential.  george hall
algorithm 772: stripack: delaunay triangulation and voronoi diagram on the surface of a sphere  stripack is a fortran 77 software package that employs an incremental algorithm to construct a delaunay triangulation and, optionally, a voronoi diagram of a set of points (nodes) on the surface of the unit sphere. the triangulation covers the convex hull of the nodes, which need not be the entire surface, while the voronoi diagram covers the entire surface. the package provides a wide range of capabilities including an efficient means of updating the triangulation with nodal additions or deletions. for n nodes, the storage requirement for the triangulation is 13n integer storage locations in addition to 3n nodal corrdinates. using an off-line algorithm and work space of size 3n, the triangulation can be constructed with time complexity o(nlogn).  robert j. renka
an algorithm for linear programming which requires o((( m+n)n< supscrpt>z+(m+n)< supscrpt>1n)) arithmetic operations  we present an algorithm for linear programming which requires  (((m \\+ n) n2 \\+ (m \\+ n)1.5 n) l) arithmetic operations where m is the number of inequalities, and n is the number of variables. each operation is performed to a precision of  (l) bits. l is bounded by the number of bits in the input.  p. m. vaidya