waashk/acm huggingface dataset:
construction of test problems in quadratic bivalent programming  a method of constructing test problems for constrained bivalent quadratic programming is presented. for any feasible integer point for a given domain, the method generates quadratic functions whose minimum over the given domain occurs at the selected point.  certain properties of unconstrained quadratic zero-one programs that determine the difficulty of the test problems are also discussed. in addition, a standardized random test problem generator for unconstrained quadratic zero- one programming is given.  panos m. pardalos
a generalized algorithm for centrality problems on trees  a general framework is presented for rapidly analyzing tree networks to compute a measure of the centrality or eccentricity of all vertices in the tree. several problems, which have been previously described in the literature, fit this framework. some of these problems have no published solution better than performing a separate traversal for each vertex whose eccentricity is calculated. the method presented in this paper performs just two traversals and yields the eccentricities of all vertices in the tree. natural sufficient conditions for the algorithm to work in linear time on any given problem are stated.  arnon rosenthal jose a. pino
on computational aspects of bounded linear least squares problems  the paper describes numerical experiments with active set methods for solving bounded linear least squares problems. it concentrates on two problems that arise in the implementation of the active set method. one problem is the choice of a good starting point. the second problem is how to move out of a "dead point." the paper investigates the use of simple iterative methods to solve these problems. the results of our experiments indicate that the use of gauss-seidel iterations to obtain a starting point is likely to provide large gains in efficiency. another interesting conclusion is that dropping one constraint at a time is advantageous to dropping several constraints at a time.  achiya dax
an iterative solution to speical linear systems on a vector hypercube  an intel hypercube implementation of a new stationary iterative method developed by one of us (jdp) is presented. this algorithm finds the solution vector x for the invertible n × n linear system ax = (i - b)x = f where a has real spectrum. the solution method converges quickly because the jacobi iteration matrix b is replaced by an equivalent iteration matrix with a smaller spectral radius. the parallel algorithm partitions a row-wise among all the processors in order to keep memory load to a minimum and to avoid duplicate computations. with the introduction of vector hardware to the hypercube, more modifications have been made to the implementation algorithm in order to exploit that hardware and reduce run-time even further. example problems and timings will be presented.  l. de pillis j. petersen j. de pillis
towards the effective parallel computation of matrix pseudospectra  given a matrix _a_, the computation of its pseudospectrum a∈ (_a_) is a far more expensive task than the computation of characteristics such as the condition number and the matrix spectrum. as research of the last 15 years has shown, however, the matrix pseudospectrum provides valuable information that is not included in other indicators. so, we ask how to compute it efficiently and build a tool that would facilitate engineers and scientists to make such analyses? in this paper we focus on parallel algorithms for computing pseudospectra. the most widely used algorithm for computing pseudospectra is embarassingly parallel; nevertheless, it is extremely costly and one cannot hope achieve absolute high performance with it. we describe algorithms that have drastically improved performance while maintaining a high degree of large grain parallelism. we evaluate the effectiveness of these methods in the context of a matlab-based environment for parallel programming using mpi on small, off-the-shelf parallel systems.  c. bekas e. kokiopoulou i. koutis e. gallopoulos
approximating sets with equivalence relations  in various considerations of computer science (for instance in image processing and databases) one faces the following situation: given a set (of points or of documents) one considers a descending sequence of equivalence relations ("approximation spaces of order "). these equivalence relations determine a sequence of closure operations cli. given a set x, the approximation sequence of x is simply <cli(x)>i> . we characterize here those sets x which satisfy the condition: x = {cli(x): i> }.  w marek h rasiowa
software for an implementation of weeks' method for the inverse laplace transform  a software package based on a modification of the weeks' method is presented for calculating function values f(t) of the inverse laplace transform. this method requires transform values f(z) at arbitrary points in the complex plane, and is suitable when f(t) has continuous derivatives of all orders; it is especially attractive when f(t) is required at a number of different abscissas t.  b. s. garbow g. giunta j. n. lyness a. murli
sweeping arrangements of curves  we consider arrangements of curves that intersect pairwise in at most k points. we show that a curve can sweep any such arrangement and maintain the k-intersection property if and only if k equals 1 or 2. we apply this result to an eclectic set of problems: finding boolean formulae for polygons with curved edges, counting triangles and digons in arrangements of pseudocircles, and finding extension curves for arrangements. we also discuss implementing the sweep.  j. snoeyink j. hershberger
size-time complexity of boolean networks for prefix computations  the prefix problem consists of computing all the products x0_x1…xj (j=0, …, n \\- 1), given a sequence x = (x0, x1, …, xn \\- 1) of elements in a semigroup. in this paper we completely characterize the size-time complexity of computing prefixes with boolean networks, which are synchronized interconnections of boolean gates and one-bit storage devices. this complexity crucially depends upon a property of the underlying semigroup, which we call cycle-freedom (no cycle of length greater than one in the cayley graph of the semigroup). denoting by s and t size and computation time, respectively, we have s = ((n/t) log(n/t)), for non-cycle-free semigroups, and s = (n/t), for cycle-free semigroups. in both cases, t ∈ [ (logn), o(n)].  g. bilardi f. p. preparata
algorithm 721; mtieu1 and mtieu2: two subroutines to compute eigenvalues and solutions to mathieu's differential equation for noninteger and integer order  two fortran routines are described which calculate eigenvalues and eigenfunctions of mathieu's differential equation for noninteger as well as integer order, mtieu1 uses standard matrix techniques with dimension parameterized to give accuracy in the eigenvalue of one part in 1012. mtieu2 used continued fraction techniques and is optimized to give accuracy in the eigenvalue of one part in 1014. the limitations of the algorithms are also discussed and illustrated.  randall b. shirts
a new inversive congruential pseudorandom number generator with power of two modulus  pseudorandom numbers are important ingredients of stochastic simulations. their quality is fundamental for the strength of the simulation outcome. the inversive congruential method for generating uniform pseudorandom numbers is a particularly attractive alternative to linear congruential generators, which show many undesirable regularities. in the present paper a new inversive congruential generator with power of two modulus is introduced. periodicity and statistical independence properties of the generated sequences are analyzed. the results show that these inversive congruential generators perform very satisfactorily.  jurgen eichenauer-herrmann holger grothe
testing isomorphism of cone graphs(extended abstract)  we give algorithms to decide graph isomorphism in a subclass of graphs which we call cone graphs. a cone graph is an undirected graph for which there exists a vertex r which uniquely determines a breadth-first search (bfs) tree. equivalently, all shortest paths from r to any other graph vertex are unique.  our algorithms may be used either nondeterministically or probabilistically. used as probabilistic algorithms, they return always a correct answer, but with an expected running time only.  christoph m. hoffmann
enhanced simulated annealing for globally minimizing functions of many- continuous variables  a new global optimization algorithm for functions of many continuous variables is presented, derived from the basic simulated annealing method. our main contribution lies in dealing with high- dimensionality minimization problems, which are often difficult to solve by all known minimization methods with or without gradient. in this article we take a special interest in the variables discretization issue. we also develop and implement several complementary stopping criteria. the original metropolis iterative random search, which takes place in a euclidean space r& lt;/bold>n, is replaced by another similar exploration, performed within a succession of euclidean spaces rp< /italic>, with p <<n. this enhanced simulated annealing (esa) algorithm was validated first on classical highly multimodal functions of 2 to 100 variables. we obtained significant reductions in the number of function evaluations compared to six other global optimization algorithms, selected according to previously published computational results for the same set of test functions. in most cases, esa was able to closely approximate known global optima. the reduced esa computational cost helped us to refine further the obtained global results, through the use of some local search. we have used this new minimizing procedure to solve complex circuit design problems, for which the objective function evaluation can be exceedingly costly.  patrick siarry gerard berthiau françois durdin jacques haussy
parallel linear programming in fixed dimension almost surely in constant time  for any fixed dimension d, thelinear programming problem with ninequality constraints can be solved on a probabilistic crcw pram witho(n)processors almost surely in constant time. the algorithm always findsthe correct solution. withnd/log2dprocessors, the probability that the algorithm will not finish withino(d2& lt;/supscrpt>log2dtime tends to zero exponentially withn.  \\---authors' abstract noga alon nimrod megiddo
random number generation with primitive pentanomials this paper presents generalized feedback shift register (gfsr) generators with primitive polynomials _x__p_ \\+ _x__p_-1 \\+ _x__q_ \\+ _x__q_-1 \\+ 1. the recurrence of these generators can be efficiently computed. we adopt fushimi's initialization scheme, which guarantees the _k_-distribution property. statistical and timing results are presented. pei-chi wu
an experimental study of methods for parallel preconditioned krylov methods  high performance multiprocessor architectures differ both in the number of processors, and in the delay costs for synchronization and communication. in order to obtain good performance on a given architecture for a given problem, adequate parallelization, good balance of load and an appropriate choice of granularity are essential.  we discuss the implementation of parallel version of pcgpak for both shared memory architectures and hypercubes. our parallel implementation is sufficiently efficient to allow us to complete the solution of our test problems on 16 processors of the encore multimax/320 in an amount of time that is a small multiple of that required by a single head of a cray x/mp, despite the fact that the peak performance of the multimax processors is not even close to the supercomputer range. we illustrate the effectiveness of our approach on a number of model problems from reservoir engineering and mathematics.  d. baxter j. saltz m. schultz s. eisenstat k. crowley
note on generalization in experimental algorithmics  a recurring theme in mathematical software evaluation is the generalization of rankings of algorithms on test problems to build knowledge-based recommender systems for algorithm selection. a key issue is to profile algorithms in terms of the qualitative characteristics of benchmark problems. in this methodological note, we adapt a novel all-pairs algorithm for the profiling task; given performance rankings for m algorithms on n problem instances, each described with p features, identify a (minimal) subset of p that is useful for assessing the selective superiority of an algorithm over another, for all pairs of m algorithms. we show how techniques presented in the mathematical software literature are inadequate for such profiling purposes. in conclusion, we also address various statistical issues underlying the effective application of this technique.  naren ramakrishnan raul e. valdes-perez
pseudorandom vector generation by the inversive method  pseudorandom vectors are of importance for parallelized simulation methods. in this article we carry out a detailed analysis of the inversive method for the generation of uniform pseudorandom vectors. this method can be viewed as an analog of the inversive congruential method for pseudorandom number generation. we study, in particular, the periodicity properties and the behavior under the serial test for sequences of pseudorandom vectors generated by the inversive method.  harald niederreiter
on translating a set of rectangles  given a collection of disjoint objects in the plane, we are interested in translating them by a common vector. if we have a primitive for translating one object at a time, then the order in which the objects can individually be translated is often geometrically constrained. in this paper we study the nature of these constraints and exhibit optimal algorithms for finding valid motion ordering for several different classes of objects. these algorithms find use in computer display applications.  leo j. guibas f. frances yao
a fourth order spline method for singular two-point boundary value problems (abstract only)  we describe a new spline method for the (weakly) singular two-point boundary value problem: (xαy)′ = f(x,y), 0 < x < 1, αε(0,1) (1) y(0) = a, y(1) = b.  we construct our spline approximation s(x) for the solution y(x) of the two- point boundary value problem (1) such that while (xαs′)′ ε c[0,1], with the uniform mesh xi = ih, i = 0(1)n, in each sub-interval [xi,si+1], our spline approximation s(x) linearly spans a certain set of (non-polynomial) basis functions in the representation of the solution y(x) of the two-point boundary value problem, and satisfies the interpolition conditions li(s) = li(y), li+1(s) = li+1(y) (2) mi(s) = mi(y), mi+1(s) = mi+1(y), where li(y) = y(xi) and mi(y) = (xαy′)′)|x=xi  the resulting method provides order h2 uniformly convergent approximations for the solution over [0, 1]. we then describe a modification of the above method. in the modified method, we generate the solution at the nodal points by using the recently proposed fourth order method of chawla [m.m. chawla, "a fourth order finite difference method based on uniform mesh for singular two-point boundary value problems", j. comput. appl. math., to appear] and then use the "conditions of continuity" to obtain the smoothed approximations for the linear functionals mi(y) needed for the construction of the spline solution. we show that the resulting method provides order h 4 uniformly convergent spline approximations for the solution y(x) over [0, 1]. the second and the fourth order of the methods described above are verified computationally.  m. m. chawla r. subramanian h. l. sathi
granularity issues for solving polynomial systems via globally convergent algorithms on a hypercube  polynomial systems of equations frequently arise in many applications such as solid modelling, robotics, computer vision, chemistry, chemical engineering, and mechanical engineering. locally convergent iterative methods such as quasi-newton methods may diverge or fail to find all meaningful solutions of a polynomial system. recently a homotopy algorithm has been proposed for polynomial systems that is guaranteed globally convergent (always converges from an arbitrary starting point) with probability one, finds all solutions to the polynomial system, and has a large amount of inherent parallelism. there are several ways the homotopy algorithms can be decomposed to run on a hypercube. the granularity of a decomposition has a profound effect on the performance of the algorithm. the results of decompositions with two different granularities are presented. the experiments were conducted on an ipsc-16 hypercube using actual industrial problems.  d. c. s. allison a. chakraborty l. t. watson
computing the block triangular form of a sparse matrix  we consider the problem of permuting the rows and columns of a rectangular or square, unsymmetric sparse matrix to compute its block triangular form. this block triangular form is based on a canonical decomposition of bipartite graphs induced by a maximum matching and was discovered by dulmage and mendelsohn. we describe implementations of algorithms to compute the block triangular form and provide computational results on sparse matrices from test collections. several applications of the block triangular form are also included.  alex pothen chin-ju fan
on computational efficiency of the iterative methods for the simultaneous approximation of polynomial zeros  a measure of efficiency of simultaneous methods for determination of polynomial zeros, defined by the coefficient of efficiency, is considered. this coefficient takes into consideration (1) the r-order of convergence in the sense of the definition introduced by ortega and rheinboldt (iterative solution of nonlinear equations in several variables. academic press, new york, 1970) and (2) the number of basic arithmetic operations per iteration, taken with certain weights depending on a processor time. the introduced definition of computational efficiency was used for comparison of the simultaneous methods with various structures.  g. v. milovanovic m. s. petkovic
desi methods for stiff initial-value problems  recently, the so-called desi (diagonally extended singly implicit) runge-kutta methods were introduced to overcome some of the limitations of singly implicit methods. preliminary experiments have shown that these methods are usually more efficient than the standard singly implicit runge-kutta (sirk) methods and, in many cases, are competitive with backward differentiation formulae (bdf). this article presents an algorithm for determining the full coefficient matrix from the stability function, which is already chosen to make the method a-stable. because of their unconventional nature, desi methods have to be implemented in a special way. in particular, the effectiveness of these methods depends heavily on how starting values are chosen for the stage iterations. these and other implementation questions are descussed in detail, and design choices we have made form the basis of an experimental coe for the solution of stiff problems by desi methods. we present here a small subset of the numerical results obtained with our code. many of these results are quite satisfactory and suggest that desi methods have a useful role in the solution of this type of problem.  j. c. butcher j. r. cash m. t. diamantakis
implementing the complex arcsine and arccosine functions using exception handling  we develop efficient algorithms for reliable and accurate evaluatins of the complex arcsine and arccosine functions. a tight error bound is derived for each algorithm; the results are valid for all machine- representable points in the complex plane. the algorithms are presented in a pseudocode that has a convenient exception-handling facility. corresponding fortran 77 programs for an ieee environment have also been developed to illustrate the practicality of the algorithms, and these programs have been tested very carefully to help confirm the correctness of the algorithms and their error bounds. the results of these tests are included in the article, but the fortran 77 programs are not (these programs are available from fairgrieve). tests of other widely available programs fail at many points in the complex plane, and otherwise are slower and produce much less accurate results.  t. e. hull thomas f. fairgrieve ping tak peter tang
performance evaluation of programs for the error and complementary error functions  this paper presents methods for performance evaluation of computer programs for the functions erf(x), erfc(x), and ex< /italic>2 erfc(x). accuracy estimates are based on comparisons using power series expansions and an expansion in the repeated integrals of erfc(x). some suggestions for checking robustness are also given. details of a specific implementation of a test program are included.  w. j. cody
an improved incomplete cholesky factorization  incomplete factorization has been shown to be a good preconditioner for the conjugate gradient method on a wide variety of problems. it is well known that allowing some fill-in during the incomplete factorization can significantly reduce the number of iterations needed for convergence. allowing fill-in, however, increases the time for the factorization and for the triangular system solutions. additionally, it is difficult to predict a priori how much fill-in to allow and how to allow it. the unpredictability of the required storage/work and the unknown benefits of the additional fill-in make such strategies impractical to use in many situations. in this article we motivate, and then present, two "black-box" strategies that significantly increase the effectiveness of incomplete cholesky factorization as a preconditioner. these strategies require no parameters from the user and do not increase the cost of the triangular system solutions. efficient implementations for these algorithms are described. these algorithms are shown to be successful for a variety of problems from the harwell-boeing sparse matrix collection.  mark t. jones paul e. plassmann
a combined unifrontal/multifrontal method for unsymmetric sparse matrices  we discuss the organization of frontal matrices in multifrontal methods for the solution of large sparse sets of unsymmetric linear equations. in the multifrontal method, work on a frontal matrix can be suspended, the frontal matrix can be stored for later reuse, and a new frontal matrix can be generated. there are thus several frontal matrices stored during the factorization, and one or more of these are assembled (summed) when creating a new frontal matrix. although this means that arbitrary sparsity patterns can be handled efficiently, extra work is required to sum the frontal matrices together and can be costly because indirect addressing is requred. the (uni)frontal method avoids this extra work by factorizing the matrix with a single frontal matrix. rows and columns are added to the frontal matrix, and pivot rows and columns are removed. data movement is simpler, but higher fill- in can result if the matrix cannot be permuted into a variable-band form with small profile. we consider a combined unifrontal/multifrontal algorithm to enable general fill-in reduction orderings to be applied without the data movement of previous multifrontal approaches. we discuss this technique in the context of a code designed for the solution of sparse systems with unsymmetric pattern.  timothy a. davis iain s. duff