waashk/acm huggingface dataset:
loss-less condensers, unbalanced expanders, and extractors  an extractor is a procedure which extracts randomness from a detective random source using a few additional random bits. explicit extractor constructions have numerous applications and obtaining such constructions is an important derandomization goal. trevisan recently introduced an elegant extractor construction, but the number of truly random bits required is suboptimal when the input source has low-min-entropy. significant progress toward overcoming this bottleneck has been made, but so far has required complicated recursive techniques that lose the simplicity of trevisan's construction.  we give a clean method for overcoming this bottleneck by constructing {\em loss-less condensers}. which compress the n-bit input source without losing any min- entropy, using o(\log n) additional random bits. our condensers are built using a simple modification of trevisan's construction, and yield the best extractor constructions to date.  loss-less condensers also produce unbalanced bipartite expander graphs with small (polylogarithmic) degree d and very strong expansion of (1-\epilon)d. we give other applications of our construction, including dispersers with entropy loss o(\log n), depth two super-concentrators whose size is within a polylog of optimal, and an improved hardness of approximation result. amnon ta-shma christopher umans david zuckerman
estimation of the inverse function for random variate generation  a regression method for estimating the inverse of a continuous cumulative probability function f(x) is presented. it is assumed that an ordered sample, x1, …, xn, of identically and independently distributed random variables is available. a reference distribution f0( x) with known inverse f0-1(p< /italic>) is used to calculate the quantities wi = i ln[f(xi)/f0(< italic>xi+1< /subscrpt>)]. these quantities are used to estimate the function γ(p) = pd ln≥f< ;subscrpt>0[f -1(p)] /dp from which an estimate of f-1(_p) is derived. the method produces an estimate in a form that is convenient for random variate generation. the procedure is illustrated using data from a study of oil and gas lease bidding.  stephen c. hora
implementing complex elementary functions using exception handling  algorithms are developed for reliable and accurate evaluations of the complex elementary functions required in fortran 77 and fortran 9, namely, cabs, csqrt, cexp, clog, csin, and ccos. the algorithms are presented in a pseudocode that has a convenient exception-handling facility. a tight error bound is derived for each algorithm. corresponding fortran 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 paper, but the fortran programs are not.  t. e. hull thomas f. fairgrieve ping-tak peter tang
efficient parallel solution of linear systems  the most efficient known parallel algorithms for inversion of a nonsingular n × n matrix a or solving a linear system ax = b over the rationals require (log n)2 time and m(n)n0.5 processors (where m(n) is the number of processors required in order to multiply two n × n rational matrices in time (log n).) furthermore, all known polylog time algorithms for those problems are unstable: they require the calculation to be done with perfect precision; otherwise they give no results at all.  this paper describes parallel algorithms that have good numerical stability and remain efficient as n grows large. in particular, we describe a quadratically convergent iterative method that gives the inverse (within the relative precision 2-no(1)) of an n × n rational matrix a with condition ≤ n0(1) in (log n)2 time using m(n) processors. this is the optimum processor bound and the factor n0.5 improvement of known processor bounds for polylog time matrix inversion. it is the first known polylog time algorithm that is numerically stable. the algorithm relies on our method of computing an approximate inverse of a that involves (log n) parallel steps and n2 processors.  also, we give a parallel algorithm for solution of a linear system ax = b with a sparse n × n symmetric positive definite matrix a. if the graph g(a) (which has n vertices and has an edge for each nonzero entry of a) is s(n)-separable, then our algorithm requires only ((log n)(log s(n))2) time and |e| + m(s(n)) processors. the algorithm computes a recursive factorization of a so that the solution of any other linear system ax = b′ with the same matrix a requires only (log n log s(n)) time and |e| + s(n)2 processors.  v pan j reif
constrained nonlinear least squares: an exact penalty approach with projected structured quasi-newton updates  this paper is concerned with the development, numerical implementation, and testing of an algorithm for solving constrained nonlinear least squares problems. the algorithm is an adaptation of the least squares case of an exact penalty method for solving nonlinearly constrained optimization problems due to coleman and conn. it also uses the ideas of nocedal and overton for handling quasi-newton updates of projected hessians, those of dennis, gay, and welsch for approaching the structure of nonlinear least squares hessians, and those of murray and overton for performing line searches. this method has been tested on a selection of problems listed in the collection of hock and schittkowski. the results indicate that the approach taken here is a viable alternative for least squares problems to the general nonlinear methods studied by hock and schittkowski.  nezam mahdavi-amiri richard h. bartels
efficient algorithms for the hitchcock transportation problem  we consider the hitchcock transportation problem on n supply points and k demand points when n is much greater than k. the problem is solved in o_(n2< italic>k log n \\+ n2 log2 n) time if n > k log k. further, applying a geometric method named splitter finding and randomization, we improve the time complexity for a case in which the ratio c of the least supply and the maximum supply satisfies the inequality log cn < n/k4 log n. indeed, if n < k5 log3 k and c = poly(n), the problem is solved in o(kn) time, which is optimal.  takeshi tokuyama jun nakano
a simple min-cut algorithm  we present an algorithm for finding the minimum cut of an undirected edge- weighted graph. it is simple in every respect. it has a short and compact description, is easy to implement, and has a surprisingly simple proof of correctness. its runtime matches that of the fastest algorithm known. the runtime analysis is straightforward. in contrast to nearly all approaches so far, the algorithm uses no flow techniques. roughly speaking, the algorithm consists of about |v| nearly identical phases each of which is a maximum adjacency search.  mechthild stoer frank wagner
algorithm 785: a software package for computing schwarz-christoffel conformal transformation for doubly connected polygonal regions  a software package implementing schwarz-christoffel conformal transformation (or mapping) of doubly connected polygonal regions is fully described in this article from mathematical, numerical, and practical perspectives. the package solves the so-called accessory parameter problem associated with the mapping function as well as evaluates forward and inverse maps. the robustness of the package is reflected by the flexibility in choosing the accuracy of the parameters to be computed, the speed of computation, the ability of mapping "difficult" regions (to be specified in section 2), and being user friendly. several examples are presented to demonstrate the capabilities of the package.  chenglie hu
admit-1: automatic differentiation and matlab interface toolbox  admit-1 enables the computation of sparse jacobian and hessian matrices, using automatic differentiation technology, from a matlab environment. given a function to be differentiated, admit-1 will exploit sparsity if present to yield sparse derivative matrices (in sparse matlab form). a generic automatic differentiation tool, subject to some functionality requirements, can be plugged into admit-1; examples include adol-c (c/c++ target functions)and admat (matlab target funcitons). admit-1 also allows for the calculation of gradients and has several other related functions. this article provides an introduction to the design and usage of admit-1.  thomas f. coleman arun verma
advanced notations in mathematica  this paper outlines the functionality and implementation of the notation package, an extension to the mathematica front end, allowing the user to introduce advanced notations. following this, several advanced example notations are presented. these include complete and functioning notations for both dirac's bra-ket notation as well as for tensorial expressions. proper functioning notations for both of these objects have not been previously presented in a major symbolic computation system, if at all.  jason harris
a technique for solving ordinary differential equations using riemann's p-functions  this paper presents an algorithmic approach to symbolic solution of 2nd order linear odes. the algorithm consists of two parts. the first part involves complete algorithms for hypergeometric equations and hypergeometric equations of confluent type. these algorithms are based on riemann's p-functions and hukuhara's p-functions respectively. another part involves an algorithm for transforming a given equation to a hypergeometric equation or a hypergeometric equation of confluent type. the transformation is possible if a given equation satisfies certain conditions, otherwise it works only as one of heuristic methods. however our method can solve many equations which seem to be very difficult to solve by conventional methods.  shunro watanabe
use of genetic algorithms for optimization in digital control of dynamic systems  this paper presents a method to optimize proportional- integral-derivative (pid) control parameters, given a discrete model of the controlled process. this method is based on holland's genetic algorithm (ga). it does not require a mathematical model of the controller to represent its dynamic behavior. it gives a solution that is not only optimal but also meets engineering constraints. genetic algorithms do a global search without derivatives for points in a multi-dimensional search space. this method works for non-linear as well as linear systems. the objective function of the ga is based on the integrated product of time and absolute error (itae). the performance of the ga is compared to that of the other optimization methods. the results show that it is simple and effective.  rajeshwar prasad srivastava
a practical parallel algorithm for solving band symmetric positive definite systems of linear equations  we give a practical parallel algorithm for solving band symmetric positive definite systems of linear equations in o(m* log n) time using nm/log n processors. here n denotes the system size and m its bandwidth. hence, the algorithm is efficient. for tridiagonal systems, the algorithm runs in o(log n) time using n/log n processors. furthermore, an improved version runs in o(log m log n) time using nm2/(log m log n) processors.  ilan bar-on
private approximation of np-hard functions  the notion of private approximation was introduced recently by feigenbaum, fong, strauss and wright. informally, a private approximation of a function f is another function f that approximates f in the usual sense, but does not yield any information on x other than what can be deduced from f(x). as such, f(x) is useful for private computation of f(x) (assuming that f can be computed more efficiently than f.  in this work we examine the properties and limitations of this new notion. specifically, we show that for many np-hard problems, the privacy requirement precludes non-trivial approximation. this is the case even for problems that otherwise admit very good approximation (e.g., problems with ptas). on the other hand, we show that slightly relaxing the privacy requirement, by means of leaking "just a few bits of informationrdquo; about x, again permits good approximation.  shai halevi robert krauthgamer eyal kushilevitz kobbi nissim
implementing a random number package with splitting facilities  a portable set of software tools is described for uniform randomvariates generation. it provides for multiple generators runningsimultaneously, and each generator has its sequence of numberspartitioned into many long (disjoint) substreams. simple procedure callsallow the user to make any generator "jump" ahead to thebeginning of its next substream, back to the beginning of its currentsubstream, or back to the beginning of its first substream.…implementation issues are discussed.…a pascal implementation for32-bit computers is described.  \\---from the authors' abstract pierre l'ecuyer serge côte
a faster algorithm for finding the minimum cut in a graph  we consider the problem of finding the minimum capacity cut in a network g with n nodes. this problem has applications to network reliability and survivability and is useful in subroutines for other network optimization problems. one can use a maximum flow problem to find a minimum cut separating a designated source node s from a designated sink node t, and by varying the sink node one can find a minimum cut in g as a sequence of at most 2n - 2 maximum flow problems. we then show how to reduce the running time of these 2n - 2 maximum flow algorithms to the running time for solving a single maximum flow problem. the resulting running time is o(nm log n2/m) for finding the minimum cut in either a directed or undirected network. the algorithm also determines the arc connectivity of either a directed or undirected network in o(nm) steps.  jianxiu hao james b. orlin
huseholder reduction of linear equations  this tutorial discusses householder reduction ofn linear equations to a triangularform which can be solved by back substitution. the main strength of themethod is its unconditional numerical stability. we explain howhouseholder reduction can be derived from elementary-matrix algebra. themethod is illustrated by a numerical example and a pascal procedure. weassume that the reader has a general knowledge of vector and matrixalgebra but is less familiar with linear transformation of a vectorspace.  \\---author's abstract per brinch hansen
generating quadratic bilevel programming test problems  this paper describes a technique for generating sparse or dense quadratic bilevel programming problems with a selectable number of known global and local solutions. the technique described here does not require the solution of any subproblems. in addition, since most techniques for solving these problems begin by solving the corresponding relaxed quadratic program, the global solutions are constructed to be different than the global solution of this relaxed problem in a selectable number of upper- and lower-level variables. finally, the problems that are generated satisfy the requirements imposed by all of the solution techniques known to the authors.  paul h. calamai luis n. vicente
a rejection technique for sampling from t-concave distributions  a rejection algorithm that uses a new method for constructing simple hat functions for a unimodal, bounded density f is introduced called "transformed density rejection." it is based on the idea of transforming f with a suitable transformation t such that t(f(x)) is concave. f is then called t-concave, and tangents of t(f(x)) in the mode and in a point on the left and right side are used to construct a hat function with a table-mountain shape. it is possible to give conditions for the optimal choice of these points of contact. with t= -1/xxx, the method can be used to construct a universal algorithm that is applicable to a large class of unimodal distributions, including the normal, beta, gamma, and t-distribution.  wolfgang hörmann
a general approximation technique for constrained forest problems  we present a general approximation technique for a large class of graph problems. our technique mostly applies to problems of covering, at minimum cost, the vertices of a graph with trees, cycles or paths satisfying certain requirements. in particular, many basic combinatorial optimization problems fit in this framework, including the shortest path, minimum spanning tree, minimum-weight perfect matching, traveling salesman and steiner tree problems.  our technique produces approximation algorithms that run in o(n~~2 log n) time and come within a factor of 2 of optimal for most of these problems. for instance, we obtain a 2-approximation algorithm for the minimum-weight perfect matching problem under the triangle inequality. our running time of o< /italic>(n2 log n) time compares favorably with the best strongly polynomial exact algorithms running in o (n3) time for dense graphs. a similar result is obtained for the 2-matching problem and its variants.we also derive the first approximation algorithms for many np- complete problems, including the non- fixed point-to-point connection problem, the exact path partitioning problem and complex location-design problems. moreover, for the prize-collecting traveling salesman or steiner tree problems, we obtain 2-approximation algorithms, therefore improving the previously best-known performance guarantees of 2.5 and 3, respectively [4].  michel x. goemans david p. williamson
kink-free deformations of polygons  we consider a discrete version of the whitney-graustein theorem concerning regular equivalence of closed curves. two regular polygons p and p', i.e. polygons without overlapping adjacent edges, are called regularly equivalent if there is a continuous one-parameter family ps, o ≥ s ≤ 1 of regular polygons with po = p and p1 = p'. geometrically the one-parameter family is a kink-free deformation transforming p into p'. the winding number of a polygon is a complete invariant of its regular equivalence class. we develop a linear algorithm that determines a linear number of elementary steps to deform a regular polygon into any other regular polygon with the same winding number.  g. vegter
a comparison of several methods of integrating stiff ordinary differential equations on parallel computing architectures  many physical systems lead to initial value problems where the system of stiff ordinary differential equations is loosely coupled. thus, in some cases the variables may be directly mapped onto sparsely connected parallel architectures such as the hypercube. this paper investigates various methods of implementing gear's algorithm on parallel computers. two conventional corrector methods utilize either functional or newton raphson iteration. we consider both alternatives and show that they exhibit similar speedups on an n node hypercube. in addition a polynomial corrector is investigated. it has the advantage of not having to solve a linear system as in the newton raphson method, yet it converges faster than functional iteration.  a. bose i. nelken j. gelfand
the solution of certain two-dimensional markov models  a class of two- dimensional birth-and-death processes, with applications in many modelling problems, is defined and analysed in the steady-state. these are processes whose instantaneous transition rates are state-dependent in a restricted way. generating functions for the steady-state distribution are obtained by solving a functional equation in two variables. that solution method lends itself readily to numerical implementation. some aspects of the numerical solution are discussed, using a particular model as an example.  g. fayolle p. j.b. king i. mitrani
gprof: a call graph execution profiler  large complex programs are composed of many small routines that implement abstractions for the routines that call them. to be useful, an execution profiler must attribute execution time in a way that is significant for the logical structure of a program as well as for its textual decomposition. this data must then be displayed to the user in a convenient and informative way. the gprof profiler accounts for the running time of called routines in the running time of the routines that call them. the design and use of this profiler is described.  susan l. graham peter b. kessler marshall k. mckusick
on the reduction of linear systems of difference equations  this paper deals with linear systems of difference equations whose coefficients admit generalized factorial series representations at z = ∞. we shall give a criterion by which a given system is determined to have a regular singularity.  in the same manner, we give an algorithm, implementable in a computer algebra system, which reduces in a finite number of steps the system of difference equations on an irreducible form.  m. a. barkatou
strongly polynomial-time and nc algorithms for detecting cycles in dynamic graphs  this paper is concerned with the problem of recognizing, in a graph with rational vector-weights associated with the edges, the existence of a cycle whose total weight is the zero vector. this problem is known to be equivalent to the problem of recognizing the existence of cycles in dynamic graphs and to the validity of some systems of recursive formulas. it was previously conjectured that combinatorial algorithms exist for the cases of two- and three-dimensional vector-weights. the present paper gives strongly polynomial algorithms for any fixed dimension. moreover, these algorithms also establish membership in the class nc. on the other hand, it is shown that when the dimension of the weights is not fixed, the problem is equivalent to the general linear programming problem under strongly polynomial and logspace reductions.  e. cohen n. megiddo
computation of the incomplete gamma function ratios and their inverse  an algorithm is given for computing the incomplete gamma function ratios p(a, x) and q>(a, x) for a 0, x 0, a \\+ x 0\\. temme's uniform asymptotic expansions are used. the algorithm is robust; results accurate to 14 significant digits can be obtained. an' extensive set of coefficients for the temme expansions is included.  an algorithm, employing third-order schroder iteration supported by newton- raphson iteration, is provided for computing x when a, p(a, x), and q(a, x) are given. three iterations at most are required to obtain 10 significant digit accuracy for x.  armido r didonato alfred h morris
a compact row storage scheme for cholesky factors using elimination trees  for a given sparse symmetric positive definite matrix, a compact row- oriented storage scheme for its cholesky factor is introduced. the scheme is based on the structure of an elimination tree defined for the given matrix. this new storage scheme has the distinct advantage of having the amount of overhead storage required for indexing always bounded by the number of nonzeros in the original matrix. the structural representation may be viewed as storing the minimal structure of the given matrix that will preserve the symbolic cholesky factor. experimental results on practical problems indicate that the amount of savings in overhead storage can be substantial when compared with sherman's compressed column storage scheme.  joseph w. liu
on the time overhead of counters and traversal markers  the problem of minimizing the time overhead of counters and traversal markers is studied. the methodology used to study the problem is based upon markov processes. a fundamental result is presented that characterizes those flowcharts where the problem can be solved uniquely in the case of counters. two methods are described that avoid poor choices of counter placement by choosing counter placements from a dominating set. with respect to the problem of traversal marker placement, the basic result that traversal markers must be placed on the complement of a uni-connected sub-graph is extended to flowcharts with circuits. finally it is shown that complements of uni- connected subgraphs that are minimal in size may not have minimal time overheads.  ira r. forman