compendia types: Published Papers(130) Journal or Magazine Articles(44) Working Papers(1) Problem Sets(1) Books(1)

research fields: Computer and Information Sciences(175) Statistics(2) Econometrics(2)

26 through 50 of 272 resultsACM Transactions on Mathematical Software

Joris Van Deun, Ronald Cools

We present an algorithm to compute integrals of the form ∫∞0 xm ∏ki = 1Jνi(aix)dx with Jνi(x) the Bessel function of the first kind and (real) order νi. The parameter m is a real number such that ∑i νi + m > −1 and the coefficients ai are strictly positive real numbers. The main ingredients in this algorithm are the well-known asymptotic expansion for Jνi(x) and the observation that the infinite part of the integral can be approximated using the incomplete Gamma function Γ(a,z). Accurate error estimates are included in the algorithm, which is implemented as a MATLAB program.

DetailsACM Transactions on Mathematical Software

Pierluigi Amodio, Giuseppe Romanazzi

BABDCR is a package of Fortran 90 subroutines for the solution of linear systems with bordered almost block diagonal coefficient matrices. It is designed to handle matrices with blocks of the same size, that is, having a block upper bidiagonal structure with an additional block in the right upper corner. The algorithm implemented in the package performs cyclic reduction of the coefficient matrix in order to reduce the fill-in due to the corner block.

DetailsACM Transactions on Mathematical Software

Eduardo N. Gonçalves, Reinaldo M. Palhares, Ricardo H. C. Takahashi, Renato C. Mesquita

This article presents a simple efficient algorithm for the subdivision of a d-dimensional simplex in kd simplices, where k is any positive integer number. The algorithm is an extension of Freudenthal's subdivision method. The proposed algorithm deals with the more general case of kd subdivision, and is considerably simpler than the RedRefinementND algorithm for implementation of Freudenthal's strategy. The proposed simplex subdivision algorithm is motivated by a problem in the field of robust control theory: the computation of a tight upper bound of a dynamical system performance index by means of a branch-and-bound algorithm.

DetailsACM Transactions on Mathematical Software

Danilo Erricolo

A translation to Fortran 90 of Gertrude Blanch's algorithm for computing the expansion coefficients of the series that represent Mathieu functions is presented. Its advantages are portability, higher precision, practicality of use, and extended documentation. In addition, numerical validations and comparisons with other existing methods are presented.

DetailsACM Transactions on Mathematical Software

Brett W. Bader, Tamara G. Kolda

Tensors (also known as multidimensional arrays or N-way arrays) are used in a variety of applications ranging from chemometrics to psychometrics. We describe four MATLAB classes for tensor manipulations that can be used for fast algorithm prototyping. The tensor class extends the functionality of MATLAB's multidimensional arrays by supporting additional operations such as tensor multiplication. The tensor_as_matrix class supports the “matricization” of a tensor, that is, the conversion of a tensor to a matrix (and vice versa), a commonly used operation in many algorithms. Two additional classes represent tensors stored in decomposed formats: cp_tensor and tucker_tensor. We describe all of ...

DetailsACM Transactions on Mathematical Software

Ioannis C. Demetriou

Fortran software is developed that calculates a best piecewise monotonic approximation to n univariate data contaminated by random errors. The underlying method minimizes the weighted sum of the squares of the errors by requiring k − 1 sign changes in the first divided differences of the approximation, where k is a given positive integer. Hence, the piecewise linear interpolant to the fit consists of k monotonic sections, alternately increasing and decreasing. This calculation can have about O(nk) local minima, because the positions of the turning points of the fit are integer variables of the problem. The method, however, by employing ...

DetailsACM Transactions on Mathematical Software

Silvano Martello, David Pisinger, Daniele Vigo, Edgar Den Boef, Jan Korst

We consider the problem of orthogonally packing a given set of rectangular-shaped boxes into the minimum number of three-dimensional rectangular bins. The problem is NP-hard in the strong sense and extremely difficult to solve in practice. We characterize relevant subclasses of packing and present an algorithm which is able to solve moderately large instances to optimality. Extensive computational experiments compare the algorithm for the three-dimensional bin packing when solving general orthogonal packings and when restricted to robot packings.

DetailsACM Transactions on Mathematical Software

Fred G. Gustavson, John K. Reid, Jerzy Waśniewski

We present subroutines for the Cholesky factorization of a positive-definite symmetric matrix and for solving corresponding sets of linear equations. They exploit cache memory by using the block hybrid format proposed by the authors in a companion article. The matrix is packed into n(n + 1)/2 real variables, and the speed is usually better than that of the LAPACK algorithm that uses full storage (n2 variables). Included are subroutines for rearranging a matrix whose upper or lower-triangular part is packed by columns to this format and for the inverse rearrangement. Also included is a kernel subroutine that is used for ...

DetailsACM Transactions on Mathematical Software

Howard C. Elman, Alison Ramage, David J. Silvester

IFISS is a graphical Matlab package for the interactive numerical study of incompressible flow problems. It includes algorithms for discretization by mixed finite element methods and a posteriori error estimation of the computed solutions. The package can also be used as a computational laboratory for experimenting with state-of-the-art preconditioned iterative solvers for the discrete linear equation systems that arise in incompressible flow modelling. A unique feature of the package is its comprehensive nature; for each problem addressed, it enables the study of both discretization and iterative solution algorithms as well as the interaction between the two and the resulting effect ...

DetailsACM Transactions on Mathematical Software

Nelson H. F. Beebe, James S. Ball

A collection of subroutines and examples of their uses are described for the quadrature method developed in the companion article. These allow the exact evaluation (up to computer truncation and rounding errors) of integrals of polynomials with two general types of logarithmic weights, and also with the corresponding nonlogarithmic weights. The recurrence coefficients for the related nonclassical orthogonal polynomials with logarithmic weight functions can also be obtained. Tests of accuracy on various platforms are presented.

The routines are usable from Fortran, C, and C++ programs conforming to any of at least six international programming-language standards.

DetailsACM Transactions on Mathematical Software

Terje O. Espelid

We discuss how to modify a recently published Matlab code, coteglob, so that the excellent performance this code demonstrates for low and intermediate accuracy requests is retained while the performance is improved for high accuracy requests. coteglob is a globally adaptive code using a 5 and 9 point pair of Newton-Cotes rules. Combining an extended sequence of rules using 5, 9, 17 and 33 points with a doubly adaptive bisection strategy is the main focus of the paper. We also discuss local versus global adaptivity and conclude that globally adaptive codes are to be preferred. Based on this we develop ...

DetailsACM Transactions on Mathematical Software

Jason W. Zwolak, Paul T. Boggs, Layne T. Watson

ODRPACK (TOMS Algorithm 676) has provided a complete package for weighted orthogonal distance regression for many years. The code is complete with user selectable reporting facilities, numerical and analytic derivatives, derivative checking, and many more features. The foundation for the algorithm is a stable and efficient trust region Levenberg-Marquardt minimizer that exploits the structure of the orthogonal distance regression problem. ODRPACK95 was created to extend the functionality and usability of ODRPACK. ODRPACK95 adds bound constraints, uses the newer Fortran 95 language, and simplifies the interface to the user called subroutine.

DetailsACM Transactions on Mathematical Software

Leonidas Linardakis, Nikos Chrisochoides

We present a geometric domain decomposition method and its implementation, which produces good domain decompositions in terms of three basic criteria: (1) The boundary of the subdomains create good angles, that is, angles no smaller than a given tolerance Φ0, where the value of Φ0 is determined by the application which will use the domain decomposition. (2) The size of the separator should be relatively small compared to the area of the subdomains. (3) The maximum area of the subdomains should be close to the average subdomain area. The domain decomposition method uses an approximation of a Medial Axis as ...

DetailsACM Transactions on Mathematical Software

Walter Schreppers, Annie Cuyt

In the past decade a number of libraries for multiprecision floating-point arithmetic have been developed. We describe an easy to use, generic C/C++ transcription program or precompiler for the conversion of C or C++ source code into new code that uses a C++ multiprecision library of choice. The precompiler can convert any type in the input source code to another type in the output source code. The input source can be either C or C++ , while the output code generated by the precompiler and using the new types, is C++. The type conversion is based on a simple XML ...

DetailsACM Transactions on Mathematical Software

Andrey N. Chernikov, Nikos P. Chrisochoides

Delaunay refinement is a widely used method for the construction of guaranteed quality triangular and tetrahedral meshes. We present an algorithm and a software for the parallel constrained Delaunay mesh generation in two dimensions. Our approach is based on the decomposition of the original mesh generation problem into N smaller subproblems which are meshed in parallel. The parallel algorithm is asynchronous with small messages which can be aggregated and exhibits low communication costs. On a heterogeneous cluster of more than 100 processors our implementation can generate over one billion triangles in less than 3 minutes, while the single-node performance is ...

DetailsACM Transactions on Mathematical Software

Marielba Rojas, Sandra A. Santos, Danny C. Sorensen

A MATLAB 6.0 implementation of the LSTRS method is presented. LSTRS was described in Rojas et al. [2000]. LSTRS is designed for large-scale quadratic problems with one norm constraint. The method is based on a reformulation of the trust-region subproblem as a parameterized eigenvalue problem, and consists of an iterative procedure that finds the optimal value for the parameter. The adjustment of the parameter requires the solution of a large-scale eigenvalue problem at each step. LSTRS relies on matrix-vector products only and has low and fixed storage requirements, features that make it suitable for large-scale computations. In the MATLAB implementation, ...

DetailsACM Transactions on Mathematical Software

R. Wang, P. Keast, P. H. Muir

In this article we discuss a new software package, BACOLR, for the numerical solution of a general class of time-dependent 1-D PDEs. This package employs high-order adaptive methods in time and space within a method-of-lines approach and provides tolerance control of the spatial and temporal errors. The DAEs resulting from the spatial discretization (based on B-spline collocation) are handled by a substantially modified version of the Runge-Kutta solver, RADAU5. For each time step, the RADAU5 code computes an estimate of the temporal error and requires it to satisfy the user tolerance. After each time step BACOLR then computes a high-order ...

DetailsACM Transactions on Mathematical Software

Steven J. Benson, Yinyu Ye

DSDP implements the dual-scaling algorithm for semidefinite programming. The source code for this interior-point algorithm, written entirely in ANSI C, is freely available under an open source license. The solver can be used as a subroutine library, as a function within the Matlab environment, or as an executable that reads and writes to data files. Initiated in 1997, DSDP has developed into an efficient and robust general-purpose solver for semidefinite programming. Its features include a convergence proof with polynomially bounded worst-case complexity, primal and dual feasible solutions when they exist, certificates of infeasibility when solutions do not exist, initial points ...

DetailsACM Transactions on Mathematical Software

Kendall E. Atkinson, Lawrence F. Shampine

We present here the algorithms and user interface of a Matlab program, Fie, that solves numerically Fredholm integral equations of the second kind on an interval [a,b] to a specified, modest accuracy. The kernel function K(s,t) is moderately smooth on [a,b] ×[a,b] except possibly across the diagonal s = t. If the interval is finite, provides for kernel functions that behave in a variety of ways across the diagonal, that is, K(s,t) may be smooth, have a discontinuity in a low-order derivative, have a logarithmic singularity, or have an algebraic singularity. Fie also solves a large class of integral equations ...

DetailsACM Transactions on Mathematical Software

Masao Kodama

The algorithm presented provides a package of subroutines for calculating the cylindrical functions Jν(x), Nν(x), Hν(1)(x), Hν(2)(x) where the order ν is complex and the real argument x is nonnegative. The algorithm is written in Fortran 95 and calculates the functions using single, double, or quadruple precision according to the value of a parameter defined in the algorithm. The methods of calculating the functions are based on a series expansion, Debye's asymptotic expansions, Olver's asymptotic expansions, and recurrence methods (Miller's algorithms). The relative errors of the functional values computed by this algorithm using double precision are less than 2.4×10 − ...

DetailsACM Transactions on Mathematical Software

Kristjan Jonasson

Matlab functions for the evaluation of the exact log-likelihood of VAR and VARMA time series models are presented (vector autoregressive moving average). The functions accept incomplete data, and calculate analytical gradients, which may be used in parameter estimation with numerical likelihood maximization. Allowance is made for possible savings when estimating seasonal, structured or distributed lag models. Also provided is a function for creating simulated VARMA time series that have an accurate distribution from term one (they are spin-up free). The functions are accompanied by a a simple example driver, a program demonstrating their use for real parameter fitting, as well ...

DetailsACM Transactions on Mathematical Software

Che-Rung Lee, G. W. Stewart

Eigentest is a package that produces real test matrices with known eigensystems. A test matrix, called an eigenmat, is generated in a factored form, in which the user can specify the eigenvalues and has some control over the condition of the eigenvalues and eigenvectors. An eigenmat A of order n requires only O(n) storage for its representation. Auxiliary programs permit the computation of (A − sI)b, (A − sI)Tb, (A − sI)−1 b, and (A − sI)−T b in O(n) operations. A special routine computes specified eigenvectors of an eigenmat and the condition of its eigenvalue. Thus eigenmats are suitable ...

DetailsACM Transactions on Mathematical Software

Osni A. Marques, Christof Vömel, James W. Demmel, Beresford N. Parlett

LAPACK is often mentioned as a positive example of a software library that encapsulates complex, robust, and widely used numerical algorithms for a wide range of applications. At installation time, the user has the option of running a (limited) number of test cases to verify the integrity of the installation process. On the algorithm developer's side, however, more exhaustive tests are usually performed to study algorithm behavior on a variety of problem settings and also computer architectures. In this process, difficult test cases need to be found that reflect particular challenges of an application or push algorithms to extreme behavior. ...

DetailsACM Transactions on Mathematical Software

Valérie Frayssé, Luc Giraud, Serge Gratton

In this article we describe our implementations of the FGMRES algorithm for both real and complex, single and double precision arithmetics suitable for serial, shared-memory, and distributed-memory computers. For the sake of portability, simplicity, flexibility, and efficiency, the FGMRES solvers have been implemented in Fortran 77 using the reverse communication mechanism for the matrix-vector product, the preconditioning, and the dot-product computations. For distributed-memory computation, several orthogonalization procedures have been implemented to reduce the cost of the dot-product calculation, which is a well-known bottleneck of efficiency for Krylov methods. Furthermore, either implicit or explicit calculation of the residual at restart is ...

DetailsACM Transactions on Mathematical Software

Joris van Deun, Karl Deckers, Adhemar Bultheel, J. A. C. Weideman

We present a numerical procedure to compute the nodes and weights in rational Gauss-Chebyshev quadrature formulas. Under certain conditions on the poles, these nodes are near best for rational interpolation with prescribed poles (in the same sense that Chebyshev points are near best for polynomial interpolation). As an illustration, we use these interpolation points to solve a differential equation with an interior boundary layer using a rational spectral method.

The algorithm to compute the interpolation points (and, if required, the quadrature weights) is implemented as a Matlab program.

Details