51 through 75 of 272 results

ACM Transactions on Mathematical Software

Hayato Waki, Sunyoung Kim, Masakazu Kojima, Masakazu Muramatsu, Hiroshi Sugimoto

SparsePOP is a Matlab implementation of the sparse semidefinite programming (SDP) relaxation method for approximating a global optimal solution of a polynomial optimization problem (POP) proposed by Waki et al. [2006]. The sparse SDP relaxation exploits a sparse structure of polynomials in POPs when applying “a hierarchy of LMI relaxations of increasing dimensions” Lasserre [2006]. The efficiency of SparsePOP to approximate optimal solutions of POPs is thus increased, and larger-scale POPs can be handled.

DetailsACM Transactions on Mathematical Software

Víctor Domínguez, Francisco-Javier Sayas

In this work we propose a new algorithm to evaluate the basis functions of the Argyris finite element and their derivatives. The main novelty here is an efficient way to calculate the matrix which gives the change of coordinates between the bases of the Argyis element for the reference and for an arbitrary triangle. This matrix is factored as the product of two rectangular matrices with a strong block structure which makes their computation very easy. We show and comment on an implementation of this algorithm in Matlab. Two numerical experiments, an interpolation of a smooth function on a triangle ...

DetailsACM Transactions on Mathematical Software

Jean Marie Linhart

We present and compare three C functions to compute the logarithm of the cumulative standard normal distribution. The first is a new algorithm derived from Algorithm 304’s calculation of the standard normal distribution via a series or continued fraction approximation, and it is good to the accuracy of the machine. The second is based on Algorithm 715’s calculation of the standard normal distribution via rational Chebyshev approximation. This is related to, and an improvement on, the algorithm for the logarithm of the normal distribution available in the software package R. The third is a new and simple algorithm that uses ...

DetailsACM Transactions on Mathematical Software

Marco Caliari, Stefanode Marchi, Marco Vianello

We present a stable and efficient Fortran implementation of polynomial interpolation at the Padua points on the square [ − 1,1]2. These points are unisolvent and their Lebesgue constant has minimal order of growth (log square of the degree). The algorithm is based on the representation of the Lagrange interpolation formula in a suitable orthogonal basis, and takes advantage of a new matrix formulation together with the machine-specific optimized BLAS subroutine for the matrix-matrix product. Extension to interpolation on rectangles, triangles and ellipses is also described.

DetailsACM Transactions on Mathematical Software

Yanqing Chen, Timothy A. Davis, William W. Hager, Sivasankaran Rajamanickam

CHOLMOD is a set of routines for factorizing sparse symmetric positive definite matrices of the form A or AAT, updating/downdating a sparse Cholesky factorization, solving linear systems, updating/downdating the solution to the triangular system Lx = b, and many other sparse matrix functions for both symmetric and unsymmetric matrices. Its supernodal Cholesky factorization relies on LAPACK and the Level-3 BLAS, and obtains a substantial fraction of the peak performance of the BLAS. Both real and complex matrices are supported. CHOLMOD is written in ANSI/ISO C, with both C and MATLABTM interfaces. It appears in MATLAB 7.2 as x = A\b ...

DetailsACM Transactions on Mathematical Software

John B. Drake, Pat Worley, Eduardo D’Azevedo

A collection of MATLAB classes for computing and using spherical harmonic transforms is presented. Methods of these classes compute differential operators on the sphere and are used to solve simple partial differential equations in a spherical geometry. The spectral synthesis and analysis algorithms using fast Fourier transforms and Legendre transforms with the associated Legendre functions are presented in detail. A set of methods associated with a spectral_field class provides spectral approximation to the differential operators ∇ ⋯, ∇ ×, ∇, and ∇2 in spherical geometry. Laplace inversion and Helmholtz equation solvers are also methods for this class. The use of ...

DetailsACM Transactions on Mathematical Software

Frédéric Cazals, Marc Pouget

Surfaces of R3 are ubiquitous in science and engineering, and estimating the local differential properties of a surface discretized as a point cloud or a triangle mesh is a central building block in computer graphics, computer aided design, computational geometry, and computer vision. One strategy to perform such an estimation consists of resorting to polynomial fitting, either interpolation or approximation, but this route is difficult for several reasons: choice of the coordinate system, numerical handling of the fitting problem, and extraction of the differential properties.

This article presents a generic C++ software package solving these problems. On the theoretical side ...

DetailsACM Transactions on Mathematical Software

Ewout van den Berg, Michael P. Friedlander, Gilles Hennenfent, Felix J. Herrmann, Rayan Saab, Özgür Yilmaz

Sparco is a framework for testing and benchmarking algorithms for sparse reconstruction. It includes a large collection of sparse reconstruction problems drawn from the imaging, compressed sensing, and geophysics literature. Sparco is also a framework for implementing new test problems and can be used as a tool for reproducible research. Sparco is implemented entirely in Matlab, and is released as open-source software under the GNU Public License.

DetailsACM Transactions on Mathematical Software

John K. Reid, Jennifer A. Scott

Fortran_Virtual_Memory is a Fortran 95 package that provides facilities for reading from and writing to direct-access files. A buffer is used to avoid actual input/output operations whenever possible. The data may be spread over many files and for very large data sets these may be held on more than one device. We describe the design of Fortran_Virtual_Memory and comment on its use within an out-of-core sparse direct solver.

DetailsACM Transactions on Mathematical Software

Kristjan Jonasson

A standard Fortran 95 module for printing scalars, vectors, and matrices to external files is provided. The module can display variables of default kind of all intrinsic types (integer, real, complex, logical, and character), and add-on modules are provided for data of the nondefault kind. The main module is self-contained and incorporating it only requires that it be compiled and linked with a program containing a “use dispmodule” statement. A generic interface and optional parameters are used, so that the same subroutine name, DISP, is used to display items of different data type and rank, irrespective of display options. The ...

DetailsACM Transactions on Mathematical Software

Robert J. Renka

TSPACK is a curve-fitting package based on exponential tension splines with automatic selection of tension factors. It serves both as a method for data fitting with preservation of shape properties or more general constraints, and as a means of computer aided geometric design of curves in two or three dimensions. The package is based on a translation of Algorithm 716 from Fortran 77 into MATLAB. The translation includes bug corrections, vectorization where possible, and extensions, including a B-spline representation, designed to facilitate curve design as opposed to data fitting. An interactive graphical user interface, not part of the algorithm, is ...

Details
Algorithm 894: On a block Schur--Parlett algorithm for ϕ-functions based on the sep-inverse estimate

ACM Transactions on Mathematical Software

Souji Koikari

FORTRAN 95 software is provided for computing the matrix values of ϕ-functions required in exponential integrators. The subroutines in the library accept as their argument a full, diagonal, or upper quasitriangular matrix with real or complex entries in one of four precisions. Two different algorithms are implemented, one is the scaling and squaring method, and the other is a modified block Schur--Parlett algorithm. In the latter algorithm, a recursive three-by-three blocking is applied to the argument based on an estimate of the sep-inverse function. The estimation of the sep-inverse function is carried out by Hager--Higham estimator implemented as the subroutine ...

DetailsACM Transactions on Mathematical Software

Franky Backeljauw, Annie Cuyt

The continued fractions for special functions package (in the sequel abbreviated as CFSF package) complements a systematic study of continued fraction representations for special functions. It provides all the functionality to create continued fractions, in particular k-periodic or limit k-periodic fractions, to compute approximants, make use of continued fraction tails, perform equivalence transformations and contractions, and much more. The package, developed in Maple, includes a library of more than 200 representations of special functions, of which only 10% can be found in the 1964 NBS Handbook of Mathematical Functions with Formulas, Graphs and Mathematical Tables by M. Abramowitz and I. ...

DetailsACM Transactions on Mathematical Software

Ladislav Lukšan, Ctirad Matonoha, Jan Vlček

We present 14 basic Fortran subroutines for large-scale unconstrained and box constrained optimization and large-scale systems of nonlinear equations. Subroutines PLIS and PLIP, intended for dense general optimization problems, are based on limited-memory variable metric methods. Subroutine PNET, also intended for dense general optimization problems, is based on an inexact truncated Newton method. Subroutines PNED and PNEC, intended for sparse general optimization problems, are based on modifications of the discrete Newton method. Subroutines PSED and PSEC, intended for partially separable optimization problems, are based on partitioned variable metric updates. Subroutine PSEN, intended for nonsmooth partially separable optimization problems, is based ...

DetailsACM Transactions on Mathematical Software

Jian He, Layne T. Watson, Masha Sosonkina

VTDIRECT95 is a Fortran 95 implementation of D. R. Jones' deterministic global optimization algorithm called DIRECT, which is widely used in multidisciplinary engineering design, biological science, and physical science applications. The package includes both a serial code and a data-distributed massively parallel code for different problem scales and optimization (exploration vs. exploitation) goals. Dynamic data structures are used to organize local data, handle unpredictable memory requirements, reduce the memory usage, and share the data across multiple processors. The parallel code employs a multilevel functional and data parallelism to boost concurrency and mitigate the data dependency, thus improving the load balancing ...

DetailsACM Transactions on Mathematical Software

Martin Albrecht, Gregory Bard, William Hart

We describe an efficient implementation of a hierarchy of algorithms for multiplication of dense matrices over the field with two elements (F2). In particular we present our implementation—in the M4RI library—of Strassen-Winograd matrix multiplication and the “Method of the Four Russians for Multiplication” (M4RM) and compare it against other available implementations. Good performance is demonstrated on AMD's Opteron processor and particulary good performance on Intel's Core 2 uo processor. The open-source M4RI library is available as a stand-alone package as well as part of the Sage mathematics system.

In machine terms, addition in F2 is logical-XOR, and multiplication is logical-AND, ...

DetailsACM Transactions on Mathematical Software

Scott A. Sarra

Global polynomial approximation methods applied to piecewise continuous functions exhibit the well-known Gibbs phenomenon. We summarize known methods to remove the Gibbs oscillations and present a collection of Matlab programs that implement the methods. The software features a Graphical User Interface that allows easy access to the postprocessing algorithms for benchmarking and educational purposes.

DetailsACM Transactions on Mathematical Software

D. S. Vlachos, T. E. Simos

LMEF is a program written in MATLAB, to calculate the coefficients of a linear multi-step method (explicit, implicit or backward differentiation formulas) with algebraic and/or exponential fitting, for the numerical solution of first order ordinary differential equations. Moreover, LMEF calculates the local truncation error and in the case of exponential fitting, the Taylor expansions of the coefficients that are necessary for the implementation of the method.

DetailsACM Transactions on Mathematical Software

Anil V. Rao, David A. Benson, Christopher Darby, Michael A. Patterson, Camila Francolin, Ilyssa Sanders, Geoffrey T. Huntington

An algorithm is described to solve multiple-phase optimal control problems using a recently developed numerical method called the Gauss pseudospectral method. The algorithm is well suited for use in modern vectorized programming languages such as FORTRAN 95 and MATLAB. The algorithm discretizes the cost functional and the differential-algebraic equations in each phase of the optimal control problem. The phases are then connected using linkage conditions on the state and time. A large-scale nonlinear programming problem (NLP) arises from the discretization and the significant features of the NLP are described in detail. A particular reusable MATLAB implementation of the algorithm, called ...

DetailsACM Transactions on Mathematical Software

Elena Celledoni, Antonella Zanna

We present two algorithms and their corresponding Fortran routines for the exact computation of free rigid body motions. The methods use the same description of the angular momentum part m by Jacobi elliptic functions, and suitably chosen frames for the attitude matrix/quaternion Q/q, respectively. The frame transformation requires the computation of elliptic integrals of the third kind. Implementation and usage of the routines are described, and some examples of drivers are included. Accuracy and performance are also tested to provide reliable numerical results.

DetailsACM Transactions on Mathematical Software

Robert Granat, Bo Kågström

We continue our presentation of parallel ScaLAPACK-style algorithms for solving Sylvester-type matrix equations. In Part II, we present SCASY (SCAlable SYlvester solvers), a state-of-the-art HPC software library for solving 44 sign and transpose variants of eight common standard and generalized Sylvester-type matrix equations.

Details
Algorithm 905: SHEPPACK: Modified Shepard Algorithm for Interpolation of Scattered Multivariate Data

ACM Transactions on Mathematical Software

William I. Thacker, Jingwei Zhang, Laynet Watson, Jeffrey B. Birch, Manjula A. Iyer, Michael W. Berry

Scattered data interpolation problems arise in many applications. Shepard’s method for constructing a global interpolant by blending local interpolants using local-support weight functions usually creates reasonable approximations. SHEPPACK is a Fortran 95 package containing five versions of the modified Shepard algorithm: quadratic (Fortran 95 translations of Algorithms 660, 661, and 798), cubic (Fortran 95 translation of Algorithm 791), and linear variations of the original Shepard algorithm. An option to the linear Shepard code is a statistically robust fit, intended to be used when the data is known to contain outliers. SHEPPACK also includes a hybrid robust piecewise linear estimation algorithm ...

DetailsACM Transactions on Mathematical Software

Tiancheng Li, Ian Robinson

A three-dimensional automatic cubature routine, called elrint3d, is described and numerical results are presented that demonstrate its applicability across a wide range of domains and integrand types. The underlying algorithm is based on a 2s-copy lattice augmentation sequence, the seed lattice for which has been determined by exhaustive search based on optimization of index of merit and trigonometric degree of precision.

DetailsACM Transactions on Mathematical Software

Timothy A. Davis, Ekanathan Palamadai Natarajan

KLU is a software package for solving sparse unsymmetric linear systems of equations that arise in circuit simulation applications. It relies on a permutation to Block Triangular Form (BTF), several methods for finding a fill-reducing ordering (variants of approximate minimum degree and nested dissection), and Gilbert/Peierls’ sparse left-looking LU factorization algorithm to factorize each block. The package is written in C and includes a MATLAB interface. Performance results comparing KLU with SuperLU, Sparse 1.3, and UMFPACK on circuit simulation matrices are presented. KLU is the default sparse direct solver in the XyceTMcircuit simulation package developed by Sandia National Laboratories.

DetailsACM Transactions on Mathematical Software

Yong-Kang Zhu, Wayne B. Hayes

We present a novel, online algorithm for exact summation of a stream of floating-point numbers. By “online” we mean that the algorithm needs to see only one input at a time, and can take an arbitrary length input stream of such inputs while requiring only constant memory. By “exact” we mean that the sum of the internal array of our algorithm is exactly equal to the sum of all the inputs, and the returned result is the correctly-rounded sum. The proof of correctness is valid for all inputs (including nonnormalized numbers but modulo intermediate overflow), and is independent of the ...

Details