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 these classes and then demonstrate their use by showing how to implement several tensor algorithms that have appeared in the literature. Categories and Subject Descriptors: G.4 [Mathematics of Computing]: Mathematical Software--Algorithm design and analysis; G.1.m [Mathematics of Computing]: Numerical Analysis--Miscellaneous General Terms: Algorithms Additional Key Words and Phrases: Higher-order tensors, multilinear algebra, N-way arrays, MATLAB
Matthey, Thierry, Cickovski, Trevor, Hampton, Scott, Ko, Alice, Ma, Qun, Nyerges, Matthew, Raeder, Troy, Slabach, Thomas, and Izaguirre, Jesus A.
ACM Transactions on Mathematical Software. Sept, 2004, Vol. 30 Issue 3, p237, 29 p.
Computer programming, Algorithm, and Algorithms
PROTOMOL is a high-performance framework in C++ for rapid prototyping of novel algorithms for molecular dynamics and related applications. Its flexibility is achieved primarily through the use of inheritance and design patterns (object-oriented programming). Performance is obtained by using templates that enable generation of efficient code for sections critical to performance (generic programming). The framework encapsulates important optimizations that can be used by developers, such as parallelism in the force computation. Its design is based on domain analysis of numerical integrators for molecular dynamics (MD) and of fast solvers for the force computation, particularly due to electrostatic interactions. Several new and efficient algorithms are implemented in PROTOMOL. Finally, it is shown that PROTOMOL'S sequential performance is excellent when compared to a leading MD program, and that it scales well for moderate number of processors. Binaries and source codes for Windows, Linux, Solaris, IRIX, HP-UX, and AIX platforms are available under open source license at http://protomol, sourceforge.net. Categories and Subject Descriptors: D.1.5 [Programming Techniques]: Object-oriented programming; D.2.11 [Software Engineering]: Software Architectures--Domain specific architectures; D.2.13 [Software Engineering]: Reusable Software--Reusable libraries; G.1.7 [Numerical Analysis]: Ordinary Differential Equations--Multistep and multivalue methods; G.4 [Mathematical Software]:Algorithm design and analysis, efficiency, parallel and vector implementations, user interfaces; J.2 [Physical Sciences and Engineering]: Chemistry, Physics; J.3 [Life and Medical Sciences]: Biology and Genetics General Terms: Algorithms, Design, Performance Additional Key Words and Phrases: Fast electrostatic methods, incremental parallelism, molecular dynamics, multigrid, multiple time-stepping integration, object-oriented framework.
ACM Transactions on Mathematical Software. March 1995, Vol. 21 Issue 1, p63, 16 p. program
Mathematical software -- Usage, FORTRAN -- Usage, Mathematical programming -- Research, and Algorithms -- Research
A system consisting of an interval data type and a symbolic form of automatic repeating differentiation is being developed for research algorithms, using Fortran 90, to solve numerical nonlinear equation and global optimization codes. This system also provides extensive data structures to remove the programming burden.
Wileden, Jack C., Clarke, Lori A., and Wolf, Alexander L.
ACM Transactions on Programming Languages & Systems. Oct 1990, Vol. 12 Issue 4, p670, 30 p. table Range of techniques.
Software Engineering, Prototype, Large-Scale Systems, Data Structures, Graphs, and Reliability
Interest in applying prototyping to the development of large-scale, production software is increasing. This brings with it a corresponding increase in efforts to develop suitable languages and tools for prototyping. Rapid development and easy modification are the two fundamental requirements for prototyping software systems. Techniques for defining data objects can be specification described, implementation described, or value described. Three implementations of object definition techniques are IRIS, a graph-based scheme to represent the semantics of software-system descriptions; GRAPHITE, a system to generate packages to manipulate directed graphs; and PIC, a language framework and analysis technique to precisely describe and analyze module interfaces.
ACM Transactions on Mathematical Software. Fall, 2015, Vol. 41 Issue 3, p17, 33 p.
Differential equations -- Analysis, Java (Computer program language) -- Analysis, and Problem solving -- Analysis
Problem-solving environments (PSEs) offer a powerful yet flexible and convenient means for general experimentation with computational methods, algorithm prototyping, and visualization and manipulation of data. Consequently, PSEs have become the modus operandi of many computational scientists and engineers. However, despite these positive aspects, PSEs typically do not offer the level of granularity required by the specialist or algorithm designer to conveniently modify the details. In other words, the level at which PSEs are black boxes is often still too high for someone interested in modifying an algorithm as opposed to trying an alternative. In this article, we describe odeToJava, a Java-based PSE for initial-value problems in ordinary differential equations. odeToJava implements explicit and linearly implicit implicit-explicit Runge-Kutta methods with error and stepsize control and intra-step interpolation (dense output), giving the user control and flexibility over the implementational aspects of these methods. We illustrate the usage and functionality of odeToJava by means of computational case studies of initial-value problems (IVPs). Categories and Subject Descriptors: D.2.11 [Software Engineering]: Software Architectures--Domain-specific architectures; Patterns; G.1.7 [Numerical Analysis]: Ordinary Differential Equations--Initial value problems; One-step (single step) methods; G.4 [Mathematical Software]: Algorithm design and analysis; User interfaces General Terms: Algorithms, Design, Experimentation Additional Key Words and Phrases: Adaptive integration, additive Runge-Kutta, geometric integration, object-oriented, problem solving environment, Runge-Kutta, software architecture, stepsize-control, Stormer-Verlet DOI: http://dx.doi.org/10.1145/2641563
This article describes the algorithms, features, and implementation of PyDEC, a Python library for computations related to the discretization of exterior calculus. PyDEC facilitates inquiry into both physical problems on manifolds as well as purely topological problems on abstract complexes. We describe efficient algorithms for constructing the operators and objects that arise in discrete exterior calculus, lowest-order finite element exterior calculus, and in related topological problems. Our algorithms are formulated in terms of high-level matrix operations which extend to arbitrary dimension. As a result, our implementations map well to the facilities of numerical libraries such as NumPy and SciPy. The availability of such libraries makes Python suitable for prototyping numerical methods. We demonstrate how PyDEC is used to solve physical and topological problems through several concise examples. Categories and Subject Descriptors: G.4 [Mathematical Software]: ; G.1.8 [Numerical Analysis]: Partial Differential Equations--Finite element methods, finite volume methods; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling--Geometric algorithms, languages, and systems General Terms: Algorithms, Theory, Experimentation, Design Additional Key Words and Phrases: Discrete exterior calculus, finite element exterior calculus, Whitney form, simplicial complex, cubical complex, Vietoris-Rips complex, computational topology, boundary operator, coboundary operator, chain, cochain DOI = 10.1145/2382585.2382588 http://doi.acm.org/10.1145/2382585.2382588
ACM Transactions on Programming Languages & Systems. April 1987, Vol. 9 Issue 2, p125, 39 p. table Peephole optimization.
Programming Language, PROLOG, Compiler/decompiler, and Algorithm
The use of Prolog as a language offers advantages for describing succinctly most of the algorithms needed in prototyping and implementing compilers, or producing tools that facilitate the task of compiling. One approach in implementing compilers using Prolog consists of coupling actions to recursive descent parsers to produce syntax-trees, which are utilized in guiding the generation of assembly code. Prolog is not only used in parsing and compiling, but is a labor-saving device in prototyping and implementing many non-numerical algorithms which arise in compiling. Unification and nondeterminism as means to circumvent costly unnecessary features are also discussed. Other topics include: bottom-up and top-down parsers; syntax-directed translation; grammar properties; code generation; and newly proposed features for compiler construction.