waashk/acm huggingface dataset:
finding all isolated solutions to polynomial systems using hompack  although the theory of polynomial continuation has been established for over a decade (following the work of garcia, zangwill, and drexler), it is difficult to solve polynomial systems using continuation in practice. divergent paths (solutions at infinity), singular solutions, and extreme scaling of coefficients can create catastrophic numerical problems. further, the large number of paths that typically arise can be discouraging. in this paper we summarize polynomial-solving homotopy continuation and report on the performance of three standard path-tracking algorithms (as implemented in hompack) in solving three physical problems of varying degrees of difficulty. our purpose is to provide useful information on solving polynomial systems, including specific guidelines for homotopy construction and parameter settings. the m-homogeneous strategy for constructing polynomial homotopies is outlined, along with more traditional approaches. computational comparisons are included to illustrate and contrast the major hompack options. the conclusions summarize our numerical experience and discuss areas for future research.  alexander p. morgan andrew j. sommese layne t. watson
an empirical study of dynamic graph algorithms  the contributions of this paper are both of theoretical and of experimental nature. from the experimental point of view, we conduct an empirical study on some dynamic connectivity algorithms which where developed recently. in particular, the following implementations were tested and compared with simple algorithms: simple sparsification by eppstein et al. and the recent randomized algorithm by henzinger and king. in our experiments, we considered both random and non- random inputs. moreover, we present a simplified variant of the algorithm by henzinger and king, which for random inputs was always faster than the original implementation. for non-random inputs, simple sparsification was the fastest algorithm for small sequences of updates; for medium and large sequences of updates, the original algorithm by henzinger and king was faster.  from the theoretical point of view, we analyze the average case running time of simple sparsification and prove that for dynamic random graphs its logarithmic overhead vanishes.  david alberts giuseppe cattaneo giuseppe f. italiano
analysis of an intrinsic overload control for a class of queueing systems  we consider a priority queueing system which consists of two queues sharing a processor and in which there is delayed feedback. such a model arises from systems which employ a priority assignment scheme to achieve overload control. an analytic expression for the stationary probability of the queue lengths is derived. an algorithm is proposed to compute the queue lengths distribution. some numerical results are illustrated.  y. t. wang
performance results of the simplex algorithm for a set of real-world linear programming models  this paper provides performance results using the sperry univac 1100 series linear programming product fmps to solve a set of 16 real-world linear programming problems. as such, this paper provides a data point for the actual performance of a commercial simplex algorithm on real- world linear programming problems and shows that the simplex algorithm is a linear time algorithm in actual performance. correlations and performance relationships not previously available are also provided.  edward h. mccall
nonlinear programming on generalized networks  we describe a specialization of the primal truncated newton algorithm for solving nonlinear optimization problems on networks with gains. the algorithm and its implementation are able to capitalize on the special structure of the constraints. extensive computational tests show that the algorithm is capable of solving very large problems. testing of numerous tactical issues are described, including maximal basis, projected line search, and pivot strategies. comparisons with nlpnet, a nonlinear network code, and minos, a general-purpose nonlinear programming code, are also included.  david p. ahlfeld john m. mulvey ron s. dembo stavros a. zenios
directed s-t numberings, rubber bands, and testing digraph k-vertexconnectivitylet g = (v, e) be a directed graph and n denote |v|. we show that g isk-vertex connected iff for every subset x of v with |x| = k, there is anembedding of g in the (k-1)-dimensional space r ;k-1, f : v -&gt;:rk-1<;/italic>, such that no hyperplane contains k points of {f(v) | v ε v}, andfor each v ε v - x, f(v) is in the convex hull of {f(w) | (v, w) ε e}. thisresult generalizes to directed graphs the notion of convex embeddings ofundirected graphs introduced by linial, lovász and wigderson in "rubber bands,convex embeddings and graph connectivity," combinatorica 8 (1988), 91-102.using this characterization, a directed graph can be tested for k-vertexconnectivity by a monte carlo algorithm in time o((m(n) + nm(k)).(log n)) witherror probability < 1/n, and by a las vegas algorithm in expected timeo((m(n)+nm(k)).k), where m(n) denotes the number of arithmetic steps formultiplying two n x n matrices (m(n) = o(n2.3755)). our monte carlo algorithmimproves on the best previous deterministic and randomized time complexitiesfor k > n0.19; e.g., for k = (n0.5, the factor of improvement is > n0.62. bothalgorithms have processor efficient parallel versions that run in o((log n)2)time on the erew pram model of computation, using a number of processors equalto (log n) times the respective sequential time complexities. our monte carloparallel algorithm improves on the number of processors used by the bestprevious (monte carlo) parallel algorithm by a factor of at least (n2/(logn)3) while having the same running time.generalizing the notion of s-t numberings, we give a combinatorialconstruction of a directed s-t numbering for any 2-vertex connected directedgraph.joseph cheriyan john h. reif
an accurate elementary mathematical library for the ieee floating point standard  the algorithms used by the ibm israel scientific center for the elementary mathematical library using the ieee standard for binary floating point arithmetic are described. the algorithms are based on the "accurate tables method." this methodology achieves high performance and produces very accurate results. it overcomes one of the main problems encountered in elementary mathematical functions computations: achieving last bit accuracy. the results obtained are correctly rounded for almost all arguement values.  our main idea in the accurate tables method is to use "nonstandard tables," which are different from the natural tables of equally spaced points in which the rounding error prevents obtaining last bit accuracy. in order to achieve a small error we use the following idea: perturb the original, equally spaced, points in such a way that the table value (or tables values in case we need several tables) will be very close to numbers which can be exactly represented by the computer (much closer than the usual double percision representation). thus we were able to control the error introduced by the computer representation of real numbers and extended the accuracy without actually using extended precision arithmetic.  shmuel gal
the design of a new frontal code for solving sparse, unsymmetric systems  we describe the design, implementation, and performance of a frontal code for the solution of large, sparse, unsymmetric systems of linear equations. the resulting software package, ma42, is included in release 11 of the harwell subroutine library and is intended to supersede the earlier ma32 package. we discuss in detail the extensive use of higher-level blas kernels within ma42 and illustrate the performance on a range of practical problems on a cray y-mp, an ibm 3090, and an ibm risc system/6000. we examine extending the frontal solution scheme to use multiple fronts to allow ma42 to be run in parallel. we indicate some directions for future development.  i. s. duff j. a. scott
superconvergent interpolants for collocation methods applied to mixed-order bvodes  continuous approximations to boundary value problems in ordinary differential equations (bvodes), constructed using collocation at gauss points, are more accurate at the mesh points than at off-mesh points. from these approximations, it is possible to construct improved continuous approximations by extending the high accuracy that is available at the mesh points to off- mesh points. one possibility is the bootstrap approach, which improves the accuracy of the approximate solution at the off-mesh points in a sequence of steps until the accuracy at the mesh points and off-mesh points is consistent. a bootstrap approach for systems of mixed-order bvodes is developed to improve approximate solutions produced by colnew, a gauss- collocation-based software package. an implementation of this approach is discussed and numerical results presented which confirm that the improved approximations satisfy the predicted error bounds and are relatively inexpensive to construct.  wayne h. enright ramanan sivasothinathan
random samples with known sample statistics: with application to variance reduction  a number of sampling schemes are described which aim to improve the accuracy of estimators in simulation experiments. the schemes negatively correlate key sample statistics in pairs of runs or blocks of runs. use is made of generators which produce random samples from certain distributions when sample statistics like the mean and dispersion are prescribed. special cases considered include normal, inverse gaussian and gamma generators. these can be used in their own right or as the basis of generators of other distributions. guide lines are given which indicate the conditions under which the schemes might be effective.  russell c.h. cheng
integration of a primal simplex network algorithm with a large-scale mathematical programming system  in this paper we discuss the implementation of a primal simplex algorithm for network problems in the mpsiii mathematical programming system. because of the need to interface with the rest of the mps this implementation is unorthodox, but computationally effective, and has a number of advantages over "stand alone" network optimizers. it is argued that a similar approach is appropriate for other general-purpose mathematical programming systems, and has applications beyond pure network optimization.  j. a. tomlin j. s. welch
approximation algorithms for max-3-cut and other problems via complex semidefinite programming  a number of recent papers on approximation algorithms have used the square roots of unity, -1 and 1 to represent binary decision variables for problems in combinatorial optimization, and have relaxed these to unit vectors in real space using semidefinite programming in order to obtain near optimal solutions to these problems. in this paper, we consider using the cube roots of unity, 1, e~~i2π/3, to represent ternary decision variables for problems in combinatorial optimization. here the natural relaxation is that of unit vectors in complex space. we use an extension of semidefinite programming to complex space to solve the natural relaxation, and use a natural extension of the random hyperplane technique introduced by the authors in [8] to obtain near-optimal solutions to the problems.  in particular, we consider the problem of maximizing the total weight of satisfied equations  xu-xv≡cmod 3 and inequations  xu-xv&amp;nequiv;cmod 3 , where  xu∈0,1,2 u. this problem can be used to model the max-3-cut problem and a directed variant we call max-3-dicut. for the general problem, we obtain a .79373-approximation algorithm. if the instance contains only inequations (as it does for max-3-cut), we obtain a performance guarantee of  7 ;12+3 4p 2arccos  2  -1/4 .83601.  this compares with proven performance guarantees of .800217 for max-3-cut (by frieze and jerrum [7]) and  3+10-8&amp;l; t;/f>  for the general problem (by andersson, engebretson, and hastad [2]). it matches the guarantee of .836008 for max-3-cut found independently by de klerk, pasechnik, and warners [4]. we show that all these algorithms are in fact identical in the case of max-3-cut.  michel x. goemans david williamson
the computation of eigenvalues and solutions of mathieu's differential equation for noninteger order  two algorithms for calculating the eigenvalues and solutions of mathieu's differential equation for noninteger order are described. in the first algorithm, leeb's method is generalized, expanding the mathieu equation in fourier series and diagonalizing the symmetric tridiagonal matrix that results. numerical testing was used to parameterize the minimum matrix dimension that must be used to achieve accuracy in the eigenvalue of one part in 1012. this method returns a set of eigenvalues below a given order and their associated solutions simultaneously. a second algorithm is presented which uses approximations to the eigenvalues (taylor series and asymptotic expansions) and then iteratively corrects the approximations using newton's method until the corrections are less than a given tolerance. a backward recursion of the continued fraction expansion is used. the second algorithm is faster and is optimized to obtain accuracy of one part in 1014, but has only been implemented for orders less than 10.5.  randall b. shirts
response time distributions for a multi-class queue with feedback  a single server queue with feedback and multiple customer classes is analyzed. arrival processes are independent poisson processes. each round of service is exponentially distributed. after receiving a round of service, a customer may depart or rejoin the end of the queue for more service. the number of rounds of service required by a customer is a random variable with a general distribution. our main contribution is characterization of response time distributions for the customer classes. our results generalize in some respects previous analyses of processor-sharing models. they also represent initial efforts to understand response time behavior along paths with loops in local balanced queueing networks.  simon s. lam a. udaya shankar
digital inversive pseudorandom numbers  a new algorithm, the digital inversive method, for generating uniform pseudorandom numbers is introduced. this algorithm starts from an inversive recursion in a large finite field and derives pseudorandom numbers from it by the digital method. if the underlying finite field has q elements, then the sequences of digital inversive pseudorandom numbers with maximum possible period length q can be characterized. sequences of multiprecision pseudorandom numbers with very large period lengths are easily obtained by this new method. digital inversive pseudorandom numbers satisfy statistical independence properties that are close to those of truly random numbers in the sense of asymptotic discrepancy. if q is a power of 2, then the digital inversive method can be implemented in a very fast manner.  jurgen eichenauer- herrmann harald niederreiter
applying series expansion to the inverse beta distribution to find percentiles of the f-distribution  let 0 ≤ 1 and f be the cumulative distribution function (cdf) of the f-distribution. we wish to find xp such that < ;italic>f(xp|n1, n2) = p, where n1 and n2 are the degrees of freedom. traditionally, xp is found using a numerical root-finding method, such as newton's method. in this paper, a procedure based on a series expansion for finding xpis given. the series expansion method has been applied to the normal, chi-square, and t distributions, but because of computational difficulties, it has not been applied to the f-distribution. these problems have been overcome by making the standard transformation to the beta distribution.  the procedure is explained in sections 3 and 4\. empirical results of a comparison of cpu times are given in section 5. the series expansion is compared to some of the standard root-finding methods. a table is given for p = .90.  roger w. abernathy robert p. smith
certification of algorithm 708: significant-digit computation of the incomplete beta  algorithm 708 (bratio) was run on 2730 test cases. comparison of these results with the results from an algorithm using a continued fraction of tretter and walster were performed using a high- precision version of the latter algorithm implemented in maple. accuracy of bratio ranged from 9.64 significant digits to a full machine double-precision, 15.65 significant digits, with the lower value occurring when a was nearly equal to b, and a was large.  barry w. brown lawrence b. levy
the k-distribution of generalized feedback shift register pseudorandom numbers  a necessary and sufficient condition is established for the generalized feedback shift register (gfsr) sequence introduced by lewis and payne to be k-distributed. based upon the theorem, a theoretical test for k-distributivity is proposed and performed in a reasonable amount of computer time, even for k = 16 and a high degree of resolution (for which statistical tests are impossible because of the astronomical amount of computer time required). for the special class of gfsr generators considered by arvillias and maritsas based on the primitive trinomial dp \\+ dq \\+ 1 with q = an integral power of 2, it is shown that the sequence is k-distributed if and only if the lengths of all subregisters are at least k. the theorem also leads to a simple and efficient method of initializing the gfsr generator so that the sequence to be generated is k-distributed.  m. fushimi s. tezuka
a dyadic determinant function  this paper proposes to define a dyadic determinant function as the n-th exterior power of an array. when the array is a square matrix and n is its row (or column) number, we obtain as a limit case the usual monadic determinant function. this approach provides a natural definition of the determinant of a non-square array as used in lagrange's identity or laplace's rule of expanding determinant. on the other hand, the successive exterior powers of a matrix provide a direct means of computing the coefficients of its characteristic polynomial.  sylvain baron
a modular system of algorithms for unconstrained minimization  we describe a new package, uncmin, for finding a local minimizer of a real valued function of more than one variable. the novel feature of uncmin is that it is a modular system of algorithms, containing three different step selection strategies (line search, dogleg, and optimal step) that may be combined with either analytic or finite difference gradient evaluation and with either analytic, finite difference, or bfgs hessian approximation. we present the results of a comparison of the three step selection strategies on the problems in more, garbow, and hillstrom in two separate cases: using finite difference gradients and hessians, and using finite difference gradients with bfgs hessian approximations. we also describe a second package, revmin, that uses optimization algorithms identical to uncmin but obtains values of user- supplied functions by reverse communication.  robert b. schnabel john e. koonatz barry e. weiss
a new look at fault tolerant network routing  consider a communication network g in which a limited number of link and/or node faults f might occur. a routing for the network (a fixed path between each pair of nodes) must be chosen without any knowledge of which components might become faulty. choosing a good routing corresponds to bounding the diameter of the surviving route graph r(g, )/f, where two nonfaulty nodes are joined by an edge if there are no faults on the route between them. we prove a number of results concerning the diameter of surviving route graphs. we show that if is a minimal length routing, then the diameter of r(g, )/f can be on the order of the number of nodes of g, even if f consists of only a single node. however, if g is the n-dimensional cube, the diameter of r(g, )/f≤3 for any minimal length routing and any set of faults f with |f| danny dolev joe halpern barbara simons ray strong
the mathematical basis and a prototype implementation of a new polynomial rootfinder with quadratic convergence  formulas developed originally by weierstrass have been used since the 1960s by many others for the simultaneous determination of all the roots of a polynomial. convergence to simple roots is quadratic, but individual approximations to a multiple root converge only linearly. however, it is shown here that the mean of such individual approximations converges quadratically to that root. this result, along with some detail about the behavior of such approximations in the neighborhood of the multiple root, suggests a new approach to the design of polynomial rootfinders. it should also be noted that the technique is well suited to take advantage of a parallel environment. this article first provides the relevant mathematical results: a short derivation of the formulas, convergence proofs, an indication of the behavior near a multiple root, and some error bounds. it then provides the outline of an algorithm based on these results, along with some graphical and numerical results to illustrate the major theoretical points. finally, a new program based on this algorithm, but with a more efficient way of choosing starting values, is described and then compared with corresponding programs from imsl and nag with good results. this program is available from mathon (combin@cs.utoronto.ca).  . t. e. hull r. mathon
overlapping batch means: something for nothing?  nonoverlapping batch means (nolbm) is a we11-known approach for estimating the variance of the sample mean. in this paper we consider an overlapping batch means (olbm) estimator that, based on the same assumptions and batch size as nolbm, has essentially the same mean and only 2/3 the asymptotic variance of nolbm. confidence interval procedures for the mean based on nolbm and olbm are discussed. both estimators are compared to the classical estimator of the variance of the mean based on sums of covariances.  marc s. meketon bruce schmeiser
expokit: a software package for computing matrix exponentials  expokit provides a set of routines aimed at computing matrix exponentials. more precisely, it computes either a small matrix exponential in full, the action of a large sparse matrix exponential on an operand vector, or the solution of a system of linear obes with constant inhomogeneity. the backbone of the sparse routines consists of matrix-free krylov subspace projection methods (arnoldi and lanczos processes), and that is why the toolkit is capable of coping with sparse matrices of large dimension. the software handles real and complex matrices and provides specific routines for symmetric and hermitian matrices. the computation of matrix exponentials is a numerical issue of critical importance in the area of markov chains and furthermore, the computed solution is subject to probabilistic constraints. in addition to addressing general matrix exponentials, a distinct attention is assigned to the computation of transient states of markov chains.  roger b. sidje
analysis and comparison of two general sparse solvers for distributed memory computers this paper provides a comprehensive study and comparison of two state-of-the-art direct solvers for large sparse sets of linear equations on large-scale distributed-memory computers. one is a multifrontal solver called mumps, the other is a supernodal solver called superlu. we describe the main algorithmic features of the two solvers and compare their performance characteristics with respect to uniprocessor speed, interprocessor communication, and memory requirements. for both solvers, preorderings for numerical stability and sparsity play an important role in achieving high parallel efficiency. we analyse the results with various ordering algorithms. our performance analysis is based on data obtained from runs on a 512-processor cray t3e using a set of matrices from real applications. we also use regular 3d grid problems to study the scalability of the two solvers.