waashk/acm huggingface dataset:
a mathematical programming generator this paper describes a mathematical programming generator that interprets problem statements written in the algebraic notation found in journal articles and text-books and outputs statements in the _mps_ format used by ibm's _mpsx_ mathematical programming system. the system has been implemented in the apl programming language. although originally designed for stand-alone use, it is currently being used as a component in an expert system that will help users formulate large linear programming models. the paper describes the syntax of the problem definition language and gives some illustrative examples. there are several unique features. first, the user can define objective function, constraint and right- hand-side coefficients as apl expressions. this leads to concise problem statements and also reduces data storage and processing requirements. second, the system supports an integrated data base query language. finally, there are a number of aids for model maintenance and sensitivity analysis. the last section of the paper describes the use of _mpgen_ in the expert system context. edward a. stohr
algorithm 768: tensolve: a software package for solving systems of nonlinear equations and nonlinear least-squares problems using tensor methods  this article describes a modular solftware package for solving systems of nonlinear equations and nonlinear problems, using a new class of methods called tensor methods. it is intended for small- to medium-sized problems, say with up to 100 equations and unknowns, in cases where it is reasonable to calculate the jacobian matrix or to approximate it by finite differences at each iteration. the software allows the user to choose between a tensor method and a standard method based on a linear model. the tensor method approximates f(x) by a quadratic model, where the second-order term is chosen so that the model is hardly more expensive to form, store, or solve than the standard linear model. moreover, the software provides two different global strategies: a line search approach and a two-dimensional trust region approach. test results indicate that, in general, tensor methods are significantly more efficient and robust than standard methods on small- and medium-sized problems in iterations and function evaluations.  ali bouaricha robert b. schnabel
bayesian networks  this brief tutorial on bayesian networks serves to introduce readers to some of the concepts, terminology, and notation employed by articles in this special section. in a bayesian network, a variable takes on values from a collection of mutually exclusive and collective exhaustive states. a variable may be discrete, having a finite or countable number of states, or it may be continuous. often the choice of states itself presents an interesting modeling question. for example, in a system for troubleshooting a problem with printing, we may choose to model the variable "print output" with two states---"present" and "absent"\---or we may want to model the variable with finer distinctions such as "absent," "blurred ," "cut off," and "ok."  david heckerman michael p. wellman
algorithm 724; program to calculate f-percentiles  let 0 p 1 be given and let f be the cumulative distribution function of the f-distribution with (m, n,) degrees of freedom. this fortran 77 routine is a complement to [1] where a method was presented to find the inverse of the f-distribution function, finv(m, n, p), using a series expansion technique to find the inverse for the beta distribution function.  roger w. abernathy robert p. smith
the solution of a combustion problem with rosenbrock methods  solving flame propagation problems with the method of lines leads to large systems of ordinary differential equations. these systems are usually solved by backward differentiation formula (bdf) methods, such as by lsode of hindmarsh. recently, rosenbrock methods turned out to be rather successful for integrating small systems with inexpensive function and jacobian evaluations. however, no test has been done on the performance of some recently developed rosenbrock codes in a situation in which the dimension of the system is large, for example, over one hundred equations. these rosenbrock codes performed quite well on the stiff detest and other small systems. the aim of this paper is to investigate the performance of the rosenbrock methods in solving the flame propagation problem by the method of lines.  a. ostermann p. kaps t. d. bui
time- and space-optimality in b-trees  a b-tree is compact if it is minimal in number of nodes, hence has optimal space utilization, among equally capacious b-trees of the same order. the space utilization of compact b-trees is analyzed and compared with that of noncompact b-trees and with (node)-visit-optimal b-trees, which minimize the expected number of nodes visited per key access. compact b-trees can be as much as a factor of 2.5 more space efficient than visit-optimal b-trees; and the node-visit cost of a compact tree is never more than 1 + the node-visit cost of an optimal tree. the utility of initializing a b-tree to be compact (which initialization can be done in time linear in the number of keys if the keys are presorted) is demonstrated by comparing the space utilization of a compact tree that has been augmented by random insertions with that of a tree that has been grown entirely by random insertions. even after increasing the number of keys by a modest amount, the effects of compact initialization are still felt. once the tree has grown so large that these effects are no longer discernible, the tree can be expeditiously compacted in place using an algorithm presented here; and the benefits of compactness resume.  arnold l. rosenberg lawrence snyder
construction of nilpotent lie algebras over arbitrary fields  in this paper we present a general description of a computationally efficient algorithm for constructing every n-dimensional nilpotent lie algebra as a central extension of a nilpotent lie algebra of dimension less than n.  as an application of the algorithm, we present a complete list of all real nilpotent six-dimensional lie algebras. since 1958, four such lists have been developed: namely, those of morozov [2], shedler [3], vergne [5] and skjelbred and sund [4]. no two of these lists agree exactly. our list resolves all the discrepancies in the other four lists. moreover, it contains each earlier list as a subset.  robert e. beck bernard kolman
intrinsically parallel multiscale algorithms for hypercubes  most algorithms implemented on parallel computers have been optimal serial algorithms, slightly modified or parallelized. an exciting possibility is the search for intrinsically parallel algorithms. these are algorithms which do not have a sensible serial equivalent --- any serial equivalent is so inefficient as to be of little use.  we describe a multiscale algorithm for the solution of pde systems that is designed specifically for massively parallel supercomputers. unlike conventional multigrid algorithms, the new algorithm utilizes the same number of processors at all times. convergence rates are much faster than for standard multigrid methods --- the solution error decreases by up to three digits per iteration. the basic idea is to solve many coarse scale problems simultaneously, combining the results in an optimal way to provide an improved fine scale solution.  on massively parallel machines the improved convergence rate is attained at no extra computational cost since processors that would otherwise be sitting idle are utilized to provide the better convergence. furthermore the algorithm is ideally suited to simd computers as well as mimd computers. on serial machines the algorithm is much slower than standard multigrid because of the extra time spent on multiple coarse scales, though in certain cases the improved convergence rate may justify this --- primarily in cases where other methods do not converge. the algorithm provides an extremely fast solution of various standard elliptic equations on machines such as the 65,536 processor connection machine, and uses only  (log(n)) parallel machine instructions to solve such equations. the discovery of this algorithm was motivated entirely by new hardware. it was a surprise to the authors to find that developments in computer architecture might lead to new mathematics. undoubtedly further intrinsically parallel algorithms await discovery.  p. frederickson o. a. mcbryan
variable precision exponential functionthe exponential function presented here returns a result which differs from_ex_ by less than one unit in the last place, for any representable value of_x_ which is not too close to values for which _ex_ would overflow orunderflow. (for values of _x_ which are not within this range, an errorcondition is raised.)it is a Â"variable precisionÂ" function in that it returns a _p_-digitapproximation for a _p_-digit argument, for any _p_ = 0 (_p_-digit means _p_-decimal-digit). the program and analysis are valid for all _p_ = 0, butcurrent implementations place a restriction on _p_.the program is presented in a pascal-like programming language callednumerical turing which has special facilities for scientific computing,including precision control, directed roundings, and built-in functions forgetting and setting exponents.t. e. hull a. abrham
a modification of talbot's method for the simultaneous approximation of several values of the inverse laplace transform  in recent years many results have been obtained in the field of the numerical inversion of laplace transforms. among them, a very accurate and general method is due to talbot: this method approximates the value of the inverse laplace transform f(t), for t fixed, using the complex values of the laplace transform f(s) sampled on a suitable contour of the complex plane. on the basis of the interest raised by talbot's method implementation, the author has been induced to investigate more deeply the possibilities of this method and has been able to generalize talbot's method, to approximate simultaneously several values of f(t) using the same sampling values of the laplace transform. in this way, the only unfavorable aspect of the classical talbot method, that is, that of recomputing all of the samples of f(s) for each t, has been eliminated.  mariarosaria rizzardi
stiffness detection and estimation of dominant spectrum with explicit runge- kutta methods  a new stiffness detection scheme based on explicit runge-kutta methods is proposed. it uses a krylov subspace approximation to estimate the eigenvalues of the jacobian of the differential system. the numerical examples indicate that this technique is a worthwhile alternative to other known stiffness detection schemes, especially when the systems are large and when it is desirable to know more about the spectrum of the jacobian than just the spectral radius.  kersti ekeland brynjulf owren eivor Øines
algorithm 738; a software package for unconstrained optimization using tensor methods  this paper describes a software package for finding the unconstrained minimizer of a nonlinear function of n variables. the package is intended for problems where n is not too large---say, n 100---so that the cost of storing one n × n matrix, and factoring it at each iteration, is acceptable. the software allows the user to choose between a recently developed "tensor method" for unconstrained optimization and an analogous standard method based on a quadratic model. the tensor method bases each iteration on a specially constructed fourth-order model of the objective function not significantly more expensive to form, store, or solve than the standard quadratic model. in our experience, the tensor method requires significantly fewer iterations and function evaluations to solve most unconstrained optimization problems than standard methods based on quadratic models, and also solves a somewhat wider range of problems. for these reasons, it may be a useful addition to numerical software libraries.  t. chow e. eskow r. schnabel
algorithm 708; significant digit computation of the incomplete beta function ratios  an algorithm is given for evaluating the incomplete beta function ratio ix(a,b) and its complement 1 - ix(a,b). a new continued fraction and a new asymptotic series are used with classical results. a transportable fortran subroutine based on this algorithm is currently in use. it is accurate to 14 significant digits when precision is not restricted by inherent error.  armido r. didonato alfred h. morris
las vegas algorithms for linear and integer programming when the dimension is small  this paper gives an algorithm for solving linear programming problems. for a problem with n constraints and d variables, the algorithm requires an expectedod2n+lognodd/2+o1+od4nlogn arithmetic operations, asn-&gt;∞. the constant factors do not depend on d. also, an algorithm is given for integer linear programming. let 4 bound the number of bits required to specify the rational numbers defining an input constraint or the objective function vector. let n and d be as before. then, the algorithm requires expected o2ddn+8dd< ;rad>nl nn&amp;l; t;/rm>lnn +dod4 lnn operations on numbers with do14 bits, as  n-&gt;∞ , where the constant factors do not depend on d or4to other convex programming problems. for example, an algorithm for finding the smallest sphere enclosing a set of n points in edhas the same time bound.  kenneth l. clarkson
on stopping criteria in verified nonlinear systems or optimization algorithms  traditionally, iterative methods for nonlinear systems use heuristic domain and range stopping criteria to determine when accuracy tolerances have been met. however, such heuristics can cause stopping at points far from actual solutions, and can be unreliable due to the effects of round-off error or inaccuracies in data. in verified computations, rigorous determination of when a set of bounds has met a tolerance can be done analogously to the traditional approximate setting. nonetheless, the range tolerance possibly cannot be met. if the criteria are used to determine when to stop subdivision of n-dimensional bounds into subregions, then failure of a range tolerance results in excessive, unnecessary subdivision, and could make the algorithm impractical. on the other hand, interval techniques can detect when inaccuracies or round-off will not permit residual bounds to be narrowed. these techniques can be incorporated into range thickness stopping criteria that complement the range stopping criteria. in this note, the issue is first introduced and illustrated with a simple example. the thickness stopping criterion is then formally introduced and analyzed. third, inclusion of the criterion within a general verified global optimization algorithm is studied. an industrial example is presented. finally, consequences and implications are discussed.  r. b. kearfott g. w. walster
approximation algorithms for constrained for constrained node weighted steiner tree problems  we consider a class of optimization problems, where the input is an undirected graph with two weight functions defined for each node, namely the node's profit and its cost. the goal is to find a connected set of nodes of low cost and high profit. we present approximation algorithms for three natural optimization criteria that arise in this context, all of which are np-hard. the budget problem asks for maximizing the profit of the set subject to a budget constraint on its cost. the quota problem requires minimizing the cost of the set subject to a quota constraint on its profit. finally, the prize collecting problem calls for minimizing the cost of the set plus the profit (here interpreted as a penalty) of the complement set. for all three problems, our algorithms give an approximation guarantee of o(\log n), where n is the number of nodes. to the best of our knowledge, these are the first approximation results for the quota problem and for the prize collecting problem, both of which are at least as hard to approximate as set cover. for the budget problem, our results improve on a previous o(\log^2 n) result of guha, moss, naor, and schieber. our methods involve new theorems relating tree packings to (node) cut conditions. we also show similar theorems (with better bounds) using edge cut conditions. these imply bounds for the analogous budget and quota problems with edge costs which are comparable to known (constant factor) bounds.  anna moss yuval rabani
optimizing locality for ode solvers  runge-kutta methods are popular methods for the solution of systems of ordinary differential equations and are provided by many scientific libraries. the performance of runge-kutta methods does not only depend on the specific application problem to be solved but also on the characteristics of the target machine. for processors with memory hierarchy, the locality of data referencing pattern has a large impact on the efficiency of a program. in this paper, we describe program transformations for runge-kutta methods resulting in programs with improved locality behavior. the transformations are based on properties of the solution method but are independent from the specific application problem or the specific target machine, so that the resulting implementation is suitable as library function. we show that the locality improvement leads to performance gains on different target machines. we also demonstrate how the locality of memory references can be further increased by exploiting the dependence structure of the right hand side function of specific ordinary differential equations.  thomas rauber gudula ruger
random number generators are chaotic  the study of highly unstable nonlinear dynamical systems---chaotic systems--- has emerged recently as an area of major interest and applicability across the mathematical, physical and social sciences. this interest has been triggered by advances in the past decade, particularly in the mathematical understanding of complex systems. an important insight that has become widely recognized in recent years is that deterministic systems can give rise to chaotic behavior. surprisingly, many of these systems are extremely simple, yet they exhibit complex chaotic behavior.  charles herring julian i. palmore
interpolants for runge-kutta formulas  a general procedure for the construction of interpolants for runge-kutta (rk) formulas is presented. as illustrations, this approach is used to develop interpolants for three explicit rk formulas, including those employed in the well-known subroutines rkf45 and dverk. a typical result is that no extra function evaluations are required to obtain an interpolant with o(h5) local truncation error for the fifth-order rk formula used in rkf45; two extra function evaluations per step are required to obtain an interpolant with  o(h6 w. h. enright k. r. jackson s. p. no:.kc /rsett p. g. thomsen
coordinate representation of order types requires exponential storage  we give doubly exponential upper and lower bounds on the size of the smallest grid on which we can embed every planar configuration of n points in general position up to order type. the lower bound is achieved by the construction of a widely dispersed "rigid" configuration which is then modified to one in general position by recent techniques of sturmfels and white, while the upper bound uses recent results of grigor'ev and vorobjou on the solution of simultaneous inequalities. this provides a sharp answer to a question first posed by chazelle.  j. e. goodman r. pollack b. sturmfels
a modified schur-complement method for handling dense columns in interior- point methods for linear programming  the main computational work in interior-point methods for linear programming (lp) is to solve a least-squares problem. the normal equations are often used, but if the lp constraint matrix contains a nearly dense column the normal- equations matrix will be nearly dense. assuming that the nondense part of the constraint matrix is of full rank, the schur complement can be used to handle dense columns. in this article we propose a modified schur-complement method that relaxes this assumption. encouraging numerical results are presented.  knud d. andersen
the convex hull of ellipsoids  the treatment of curved algebraic surfaces becomes more and more the f ocus of attention in computational geometry. we present a video that illustrates the computation of the convex hull of a set of ellipsoids. the underlying algorithm is an application of our work on determining a cell in a 3-dimensional arrangement of quadrics, see \cite{ghs-ccaq-01}. in the video, the main emphasis is on a simple and comprehensible visualization of the geometric aspects of the algorithm. in addition, we give some insights into the underlying mathematical problems.  nicola geismann michael hemmer elmar schömer
simple multivariate time series for simulations of complex systems  recent work has made the generation of univariate time series for inputs to stochastic systems quite simple. the time series are all random linear combinations of i.i.d. random variables with exponential, gamma and hyperexponential marginal distributions. the simplicity of structure of these time series models makes it practical to combine them to model multivariate situations. thus one can model, for example, alternating sequences of response and think times at a terminal in which response and think times are not only autocorrelated, but also crosscorrelated.  peter a. w. lewis
edge concentration: a method for clustering directed graphs  the display of a directed graph is a commonly used visual aid for representing relationships. however, some graphs contain so many edges that their display by traditional graph layout algorithms is virtually impossible because of the overwhelming number of crossings. graphs representing large software systems and their configurations are particularly prone to this problem. examples of such graphs include: graphs depicting a system's configuration, call graphs, graphs depicting import and export relationships between modules, and graphs depicting the "includes" relation among a system's source files.  this paper proposes the elimination of some edges by replacing sets of edges that have the same set of source and target nodes by a special node called an edge concentration node. reducing the number of edges often has the desirable side effect of reducing the number of crossings. an algorithm that determines a reasonable set of edge concentrations of a graph in (n4) operations for each level in the graph is presented where n is the number of nodes in that level. several examples from the area of software configuration management are shown to demonstrate the effectiveness of using edge concentrations.  f. j. newbery
the software engineering learning facility  the software engineering learning facility (self) is a web-based environment designed to enhance learning the art of software development. the system consists of three components. the _practice component_ enables students to solve problems related to language constructs and algorithms. the _process component_ guides students through a waterfall model of software development, emphasizing product development and verification. the _performance component_ monitors progress and provides feedback for improving each student's personal software development process. this paper reports on the motivation and design of the system, the state of its implementation, and lessons learned.  larry morell david middleton