Sparse matrix vector multiplication (SpMV) is an important computational kernel in traditional high-performance computing and emerging data-intensive applications. Previous SpMV libraries are optimized by either application-specific or architecture-specific approaches but present difficulties for use in real applications. In this work, we develop an auto-tuning system (SMATER) to bridge the gap between specific optimizations and general-purpose use. SMATER provides programmers a unified interface based on the compressed sparse row (CSR) sparse matrix format by implicitly choosing the best format and fastest implementation for any input sparse matrix during runtime. SMATER leverages a machine-learning model and retargetable back-end library to quickly predict the optimal combination. PubDate: Thu, 09 Aug 2018 00:00:00 GMT

Abstract: Gianluca Frison, Dimitris Kouzoupis, Tommaso Sartor, Andrea Zanelli, Moritz Diehl

Basic Linear Algebra Subroutines for Embedded Optimization (BLASFEO) is a dense linear algebra library providing high-performance implementations of BLAS- and LAPACK-like routines for use in embedded optimization and small-scale high-performance computing, in general. A key difference with respect to existing high-performance implementations of BLAS is that the computational performance is optimized for small- to medium-scale matrices, i.e., for sizes up to a few hundred. BLASFEO comes with three different implementations: a high-performance implementation aimed at providing the highest performance for matrices fitting in cache, a reference implementation providing portability and embeddability and optimized for very small matrices, and a wrapper to standard BLAS and LAPACK providing high performance on large matrices. PubDate: Tue, 31 Jul 2018 00:00:00 GMT

Abstract: Wen Huang, P.-A. Absil, Kyle A. Gallivan, Paul Hand

Riemannian optimization is the task of finding an optimum of a real-valued function defined on a Riemannian manifold. Riemannian optimization has been a topic of much interest over the past few years due to many applications including computer vision, signal processing, and numerical linear algebra. The substantial background required to successfully design and apply Riemannian optimization algorithms is a significant impediment for many potential users. Therefore, multiple packages, such as Manopt (in Matlab) and Pymanopt (in Python), have been developed. This article describes ROPTLIB, a C++ library for Riemannian optimization. PubDate: Tue, 31 Jul 2018 00:00:00 GMT

Abstract: Florent Bréhard, Nicolas Brisebarre, Mioara Joldeş

In this work, we develop a validated numeric method for the solution of linear ordinary differential equations (LODEs). A wide range of algorithms (i.e., Runge-Kutta, collocation, spectral methods) exist for numerically computing approximations of the solutions. Most of these come with proofs of asymptotic convergence, but usually, provided error bounds are nonconstructive. However, in some domains like critical systems and computer-aided mathematical proofs, one needs validated effective error bounds. We focus on both the theoretical and practical complexity analysis of a so-called a posteriori quasi-Newton validation method, which mainly relies on a fixed-point argument of a contracting map. Specifically, given a polynomial approximation, obtained by some numerical algorithm and expressed on a Chebyshev basis, our algorithm efficiently computes an accurate and rigorous error bound. PubDate: Tue, 31 Jul 2018 00:00:00 GMT

Permutation problems are combinatorial optimization problems whose solutions are naturally codified as permutations. Due to their complexity, motivated principally by the factorial cardinality of the search space of solutions, they have been a recurrent topic for the artificial intelligence and operations research community. Recently, among the vast number of metaheuristic algorithms, new advances on estimation of distribution algorithms (EDAs) have shown outstanding performance when solving some permutation problems. These novel EDAs implement distance-based exponential probability models such as the Mallows and Generalized Mallows models. In this article, we present a Matlab package, perm_mateda, of estimation of distribution algorithms on permutation problems, which has been implemented as an extension to the Mateda-2.0 toolbox of EDAs. PubDate: Thu, 26 Jul 2018 00:00:00 GMT

For configurations of point-sets that are pairwise constrained by distance intervals, the EASAL software implements a suite of algorithms that characterize the structure and geometric properties of the configuration space. The algorithms generate, describe, and explore these configuration spaces using generic rigidity properties, classical results for stratification of semi-algebraic sets, and new results for efficient sampling by convex parametrization. The article reviews the key theoretical underpinnings, major algorithms, and their implementation. The article outlines the main applications such as the computation of free energy and kinetics of assembly of supramolecular structures or of clusters in colloidal and soft materials. PubDate: Thu, 26 Jul 2018 00:00:00 GMT

Pseudo-random number generators (PRNGs) play an important role in both areas of computer simulation and computer security. Currently, there appears to be a huge divide between the types of PRNGs used in these two areas. For PRNGs in computer security applications, the security concern is extremely important. For PRNGs in computer simulation applications, the properties of high-dimensional equi-distribution, efficiency, long period-length, and portability are important. In recent years, there have been many PRNGs proposed in the area of computer simulation satisfying these nice properties. However, most of them are linear generators, thus sharing the same weakness in predictability. The major aim of this article is to propose a general class of secure generators, called SAFE (secure and fast encryption) generators, by properly “mixing” two baseline generators with the aforementioned properties to obtain a secure generator that would inherit these nice properties. PubDate: Sat, 14 Jul 2018 00:00:00 GMT

One of the challenges in computational modeling is coupling models to solve multidisciplinary problems. Flow-based computational frameworks alleviate part of the challenge through a modular approach, where data flows from component to component. However, existing flow-based frameworks are inefficient when coupled derivatives are needed for optimization. To address this, we develop the modular analysis and unified derivatives (MAUD) architecture. MAUD formulates the multidisciplinary model as a nonlinear system of equations, which leads to a linear equation that unifies all methods for computing derivatives. This enables flow-based frameworks that use the MAUD architecture to provide a common interface for the chain rule, adjoint method, coupled adjoint method, and hybrid methods; MAUD automatically uses the appropriate method for the problem. PubDate: Sat, 16 Jun 2018 00:00:00 GMT

Abstract: Ioannis Z. Emiris, Vissarion Fisikopoulos

We experimentally study the fundamental problem of computing the volume of a convex polytope given as an intersection of linear halfspaces. We implement and evaluate randomized polynomial-time algorithms for accurately approximating the polytope’s volume in high dimensions (e.g., few hundreds) based onhit-and-run random walks. To carry out this efficiently, we experimentally correlate the effect of parameters, such as random walk length and number of sample points, with accuracy and runtime. Our method is based on Monte Carlo algorithms with guaranteed speed and provably high probability of success for arbitrarily high precision. We exploit the problem’s features in implementing a practical rounding procedure of polytopes, in computing only partial “generations” of random points, and in designing fast polytope boundary oracles. PubDate: Sat, 16 Jun 2018 00:00:00 GMT

Abstract: Pasqua D’ambra, Salvatore Filippone, Panayot S. Vassilevski

This article has two main objectives: one is to describe some extensions of an adaptive Algebraic Multigrid (AMG) method of the form previously proposed by the first and third authors, and a second one is to present a new software framework, named BootCMatch, which implements all the components needed to build and apply the described adaptive AMG both as a stand-alone solver and as a preconditioner in a Krylov method. The adaptive AMG presented is meant to handle general symmetric and positive definite (SPD) sparse linear systems, without assuming any a priori information of the problem and its origin; the goal of adaptivity is to achieve a method with a prescribed convergence rate. PubDate: Sat, 16 Jun 2018 00:00:00 GMT

Abstract: Adolfo R. Escobedo, Erick Moreno-Centeno, Christopher Lourenco

Exact solving of systems of linear equations (SLEs) is a fundamental subroutine within number theory, formal verification of mathematical proofs, and exact-precision mathematical programming. Moreover, efficient exact SLE solution methods could be valuable for a growing body of science and engineering applications where current fixed-precision standards have been deemed inadequate. This article contains key derivations relating, and computational tests comparing, two exact direct solution frameworks: roundoff-error-free (REF) LU factorization and rational arithmetic LU factorization. Specifically, both approaches solve the linear system Ax=b by factoring the matrix A into the product of a lower triangular (L) and upper triangular (U) matrix, A=LU. PubDate: Sat, 16 Jun 2018 00:00:00 GMT

A long-standing problem related to floating-point implementation of numerical programs is to provide efficient yet precise analysis of output errors. We present a framework to compute lower bounds on largest absolute roundoff errors, for a particular rounding model. This method applies to numerical programs implementing polynomial functions with box constrained input variables. Our study is based on three different hierarchies, relying respectively on generalized eigenvalue problems, elementary computations, and semidefinite programming (SDP) relaxations. This is complementary of over-approximation frameworks, consisting of obtaining upper bounds on the largest absolute roundoff error. Combining the results of both frameworks allows one to get enclosures for upper bounds on roundoff errors. PubDate: Sat, 16 Jun 2018 00:00:00 GMT