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)

76 through 100 of 272 resultsACM Transactions on Mathematical Software

Sébastien Le Digabel

NOMAD is software that implements the Mesh Adaptive Direct Search (MADS) algorithm for blackbox optimization under general nonlinear constraints. Blackbox optimization is about optimizing functions that are usually given as costly programs with no derivative information and no function values returned for a significant number of calls attempted. NOMAD is designed for such problems and aims for the best possible solution with a small number of evaluations. The objective of this article is to describe the underlying algorithm, the software’s functionalities, and its implementation.

DetailsACM Transactions on Mathematical Software

Christopher Kormanyos

This article presents a portable C++ system for multiple precision calculations of special functions called e_float. It has an extendable architecture with a uniform C++ layer which can be used with any suitably prepared MP type. The system implements many high-precision special functions and extends some of these to very large parameter ranges. It supports calculations with 30 ⋯ 300 decimal digits of precision. Interoperabilities with Microsoft’s® CLR, Python, and Mathematica® are supported. The e_float system and its usage are described in detail. Implementation notes, testing results, and performance measurements are provided.

DetailsACM Transactions on Mathematical Software

David M. Smith

This article describes a collection of Fortran-95 routines for evaluating the exponential integral function, error function, sine and cosine integrals, Fresnel integrals, Bessel functions, and related mathematical special functions using the FM multiple-precision arithmetic package.

DetailsACM Transactions on Mathematical Software

Masao Kodama

The present algorithm provides a module for calculating the cylindrical functions Jv(z), Yv(z), Hv(1)(z), and Hv(2)(z), where the order v is complex and the complex argument z satisfies −π < arg z ≤ π. The algorithm is written in Fortran 90 and calculates the functions using real and complex numbers of any intrinsic data type whose kind type parameter the user’s Fortran system accepts. The methods of calculating the functions are based on two kinds of series expansions and numerical integration. Wronskian tests examine the functional values computed by this algorithm with double precision at 4,100,625 pseudorandom test points in ...

DetailsACM Transactions on Mathematical Software

Martin B. Van Gijzen, Peter Sonneveld

The IDR(s) method that is proposed in Sonneveld and van Gijzen [2008] is a very efficient limited memory method for solving large nonsymmetric systems of linear equations. IDR(s) is based on the induced dimension reduction theorem, that provides a way to construct subsequent residuals that lie in a sequence of shrinking subspaces. The IDR(s) algorithm that is given in Sonneveld and van Gijzen [2008] is a direct translation of the theorem into an algorithm. This translation is not unique. This article derives a new IDR(s) variant, that imposes (one-sided) biorthogonalization conditions on the iteration vectors. The resulting method has lower ...

DetailsACM Transactions on Mathematical Software

Amparo Gil, Javier Segura, Nico M. Temme

A Fortran 90 program for the computation of the real parabolic cylinder functions W(a, ± x), x ≥ 0 and their derivatives is presented. The code also computes scaled functions for a > 50. The functions W(a, ± x) are a numerically satisfactory pair of solutions of the parabolic cylinder equation y′ + (x2/4 − a)y = 0, x ≥ 0. Using Wronskian tests, we claim a relative accuracy better than 5 10−13 in the computable range of unscaled functions, while for scaled functions the aimed relative accuracy is better than 5 10−14. This code, together with the algorithm and ...

DetailsACM Transactions on Mathematical Software

Timothy A. Davis

SuiteSparseQR is a sparse QR factorization package based on the multifrontal method. Within each frontal matrix, LAPACK and the multithreaded BLAS enable the method to obtain high performance on multicore architectures. Parallelism across different frontal matrices is handled with Intel's Threading Building Blocks library. The symbolic analysis and ordering phase pre-eliminates singletons by permuting the input matrix A into the form [R11 R12; 0 A22] where R11 is upper triangular with diagonal entries above a given tolerance. Next, the fill-reducing ordering, column elimination tree, and frontal matrix structures are found without requiring the formation of the pattern of ATA. Approximate ...

DetailsACM Transactions on Mathematical Software

Mofreh R. Zaghloul, Ahmed N. Ali

We present a MATLAB function for the numerical evaluation of the Faddeyeva function w(z). The function is based on a newly developed accurate algorithm. In addition to its higher accuracy, the software provides a flexible accuracy vs efficiency trade-off through a controlling parameter that may be used to reduce accuracy and computational time and vice versa. Verification of the flexibility, reliability, and superior accuracy of the algorithm is provided through comparison with standard algorithms available in other libraries and software packages.

DetailsACM Transactions on Mathematical Software

Miloud Sadkane, Ahmed Touhami

Given a regular matrix pencil λB -- A and a positively oriented contour γ in the complex plane, the spectral dichotomy methods applied to λB -- A and γ consist in determining whether λB -- A possesses eigenvalues on or in a neighborhood of γ. When no such eigenvalues exist, these methods compute iteratively the spectral projector P onto the right deflating subspace of λB -- A associated with the eigenvalues inside/outside γ. The computation of the projector is accompanied by the spectral norm ||H|| of a Hermitian positive definite matrix H called the dichotomy condition number, which indicates the ...

DetailsACM Transactions on Mathematical Software

Jitse Niesen, Will M. Wright

We develop an algorithm for computing the solution of a large system of linear ordinary differential equations (ODEs) with polynomial inhomogeneity. This is equivalent to computing the action of a certain matrix function on the vector representing the initial condition. The matrix function is a linear combination of the matrix exponential and other functions related to the exponential (the so-called ϕ-functions). Such computations are the major computational burden in the implementation of exponential integrators, which can solve general ODEs. Our approach is to compute the action of the matrix function by constructing a Krylov subspace using Arnoldi or Lanczos iteration ...

DetailsACM Transactions on Mathematical Software

Sunyoung Kim, Masakazu Kojima, Hayato Waki, Makato Yamashita

SFSDP is a Matlab package for solving sensor network localization (SNL) problems. These types of problems arise in monitoring and controlling applications using wireless sensor networks. SFSDP implements the semidefinite programming (SDP) relaxation proposed in Kim et al. [2009] for sensor network localization problems, as a sparse version of the full semidefinite programming relaxation (FSDP) by Biswas and Ye [2004]. To improve the efficiency of FSDP, SFSDP exploits the aggregated and correlative sparsity of a sensor network localization problem. As a result, SFSDP can handle much larger problems than other software as well as three-dimensional anchor-free problems. SFSDP analyzes the ...

DetailsACM Transactions on Mathematical Software

Jonathan D. Hauenstein, Frank Sottile

Smale’s α-theory uses estimates related to the convergence of Newton’s method to certify that Newton iterations will converge quadratically to solutions to a square polynomial system. The program alphaCertified implements algorithms based on α-theory to certify solutions of polynomial systems using both exact rational arithmetic and arbitrary precision floating point arithmetic. It also implements algorithms that certify whether a given point corresponds to a real solution, and algorithms to heuristically validate solutions to overdetermined systems. Examples are presented to demonstrate the algorithms.

DetailsACM Transactions on Mathematical Software

Xia Ji, Jiguang Sun, Tiara Turner

Transmission eigenvalue problem has important applications in inverse scattering. Since the problem is non-self-adjoint, the computation of transmission eigenvalues needs special treatment. Based on a fourth-order reformulation of the transmission eigenvalue problem, a mixed finite element method is applied. The method has two major advantages: 1) the formulation leads to a generalized eigenvalue problem naturally without the need to invert a related linear system, and 2) the nonphysical zero transmission eigenvalue, which has an infinitely dimensional eigenspace, is eliminated. To solve the resulting non-Hermitian eigenvalue problem, an iterative algorithm using restarted Arnoldi method is proposed. To make the computation efficient, ...

DetailsACM Transactions on Mathematical Software

M. Wimmer

Computing the Pfaffian of a skew-symmetric matrix is a problem that arises in various fields of physics. Both computing the Pfaffian and a related problem, computing the canonical form of a skew-symmetric matrix under unitary congruence, can be solved easily once the skew-symmetric matrix has been reduced to skew-symmetric tridiagonal form. We develop efficient numerical methods for computing this tridiagonal form based on Gaussian elimination, using a skew-symmetric, blocked form of the Parlett-Reid algorithm, or based on unitary transformations, using block Householder transformations and Givens rotations, that are applicable to dense and banded matrices, respectively. We also give a complete ...

DetailsACM Transactions on Mathematical Software

Alberto Abad, Roberto Barrio, Fernando Blesa, Marcos Rodríguez

This article introduces the software package TIDES and revisits the use of the Taylor series method for the numerical integration of ODEs. The package TIDES provides an easy-to-use interface for standard double precision integrations, but also for quadruple precision and multiple precision integrations. The motivation for the development of this package is that more and more scientific disciplines need very high precision solution of ODEs, and a standard ODE method is not able to reach these precision levels. The TIDES package combines a preprocessor step in Mathematica that generates Fortran or C programs with a library in C. Another capability ...

DetailsACM Transactions on Mathematical Software

Makoto Yamashita, Katsuki Fujisawa, Mituhiro Fukuda, Kazuhide Nakata, Maho Nakata

A SemiDefinite Programming (SDP) problem is one of the most central problems in mathematical optimization. SDP provides an effective computation framework for many research fields. Some applications, however, require solving a large-scale SDP whose size exceeds the capacity of a single processor both in terms of computation time and available memory. SDPARA (SemiDefinite Programming Algorithm paRAllel package) [Yamashita et al. 2003b] was designed to solve such large-scale SDPs. Its parallel performance is outstanding for general SDPs in most cases. However, the parallel implementation is less successful for some sparse SDPs obtained from applications such as Polynomial Optimization Problems (POPs) or ...

DetailsACM Transactions on Mathematical Software

Ian Thompson

An algorithm for accurately computing the lower incomplete gamma function γ(a, t) in the case where a = n + 1/2, n ∈ Z and t < 0 is described. Series expansions and analytic continuation are employed to compute the function for certain critical values of n, and these results are used to initiate stable recurrence. The algorithm has been implemented in Fortran 2003, with precompuations carried out in Maple.

DetailsACM Transactions on Mathematical Software

J. R. Cash, D. Hollevoet, F. Mazzia, A. M. Nagy

In this article we describe the code bvptwp.m, a MATLAB code for the solution of two point boundary value problems. This code is based on the well-known Fortran codes, twpbvp.f, twpbvpl.f and acdc.f, that employ a mesh selection strategy based on the estimation of the local error, and on revisions of these codes, called twpbvpc.f, twpbvplc.f and acdcc.f, that employ a mesh selection strategy based on the estimation of the local error and the estimation of two parameters which characterize the conditioning of the problem. The codes twpbvp.f/tpbvpc.f use a deferred correction scheme based on Mono-Implicit Runge-Kutta methods (MIRK); the ...

DetailsACM Transactions on Mathematical Software

Joseph Rios

Dantzig--Wolfe Decomposition is recognized as a powerful, algorithmic tool for solving linear programs of block-angular form. While use of the approach has been reported in a wide variety of domains, there has not been a general implementation of Dantzig--Wolfe decomposition available. This article describes an open-source implementation of the algorithm. It is general in the sense that any properly decomposed linear program can be provided to the software for solving. While the original description of the algorithm was motivated by its reduced memory usage, modern computers can also take advantage of the algorithm's inherent parallelism. This implementation is parallel and ...

DetailsACM Transactions on Mathematical Software

Mani Mehra, Kavita Goyal

A collection of the Matlab routines that compute the values of the scaling and wavelet functions ([HTML_REMOVED](x) and ψ(x) respectively) and the derivative of an arbitrary function (periodic or non periodic) using wavelet bases is presented. Initially, the case of Daubechies wavelets is taken and the procedure is explained for both collocation and Galerkin approaches. For each case a Matlab routine is provided to compute the differentiation matrix and the derivative of the function f(d) = D(d)f. Moreover, the convergence of the derivative is shown graphically as a function of different parameters (the wavelet genus, D and the scale, J) ...

DetailsACM Transactions on Mathematical Software

Timothy A. Davis

The MATLAB™ backslash (x=A\b) is an elegant and powerful interface to a suite of high-performance factorization methods for the direct solution of the linear system Ax = b and the least-squares problem minx ‖b - Ax‖. It is a meta-algorithm that selects the best factorization method for a particular matrix, whether sparse or dense. However, the simplicity and elegance of its single-character interface prohibits the reuse of its factorization for subsequent systems. Requiring MATLAB users to find the best factorization method on their own can lead to suboptimal choices; even MATLAB experts can make the wrong choice. Furthermore, naive MATLAB ...

DetailsACM Transactions on Mathematical Software

Wenrui Hao, Andrew J. Sommese, Zhonggang Zeng

A Matlab implementation, multiplicity, of a numerical algorithm for computing the multiplicity structure of a nonlinear system at an isolated zero is presented. The software incorporates a newly developed equation-by-equation strategy that significantly improves the efficiency of the closedness subspace algorithm and substantially reduces the storage requirement. The equation-by-equation strategy is actually based on a variable-by-variable closedness subspace approach. As a result, the algorithm and software can handle much larger nonlinear systems and higher multiplicities than their predecessors, as shown in computational experiments on the included test suite of benchmark problems.

DetailsACM Transactions on Mathematical Software

Martin J. Gander, Caroline Japhet

We design and analyze an algorithm with linear complexity to perform projections between 2D and 3D nonmatching grids. This algorithm, named the PANG algorithm, is based on an advancing front technique and neighboring information. Its implementation is surprisingly short, and we give the entire Matlab code. For computing the intersections, we use a direct and numerically robust approach. We show numerical experiments both for 2D and 3D grids, which illustrate the optimal complexity and negligible overhead of the algorithm. An outline of this algorithm has already been presented in a short proceedings paper of the 18th International Conference on Domain ...

DetailsACM Transactions on Mathematical Software

Leslie V. Foster, Timothy A. Davis

The SPQR_RANK package contains routines that calculate the numerical rank of large, sparse, numerically rank-deficient matrices. The routines can also calculate orthonormal bases for numerical null spaces, approximate pseudoinverse solutions to least squares problems involving rank-deficient matrices, and basic solutions to these problems. The algorithms are based on SPQR from SuiteSparseQR (ACM Transactions on Mathematical Software 38, Article 8, 2011). SPQR is a high-performance routine for forming QR factorizations of large, sparse matrices. It returns an estimate for the numerical rank that is usually, but not always, correct. The new routines improve the accuracy of the numerical rank calculated by ...

DetailsACM Transactions on Mathematical Software

Danilo Erricolo, Giuseppe Carluccio

Software to compute angular and radial Mathieu functions is provided in the case that the parameter q is a complex variable and the independent variable x is real. After an introduction on the notation and the definitions of Mathieu functions and their related properties, Fortran 90 subroutines to compute them are described and validated with some comparisons. A sample application is also provided.

Details