Abstract Inverse problems occur in many scientific fields. Albeit grid search, where points of a regular grid are tested as possible solutions, is a straightforward and robust method to numerically solve inverse problems, it is computationally intensive and becomes prohibitive when the problem has a high dimensionality. Heterogeneous clusters are a viable and cost-effective solution to exploit the combined computational power of multiple available computers. In this paper, we present a computing framework that supports efficient grid search for inverse problems on heterogeneous clusters. Scheduling the workload on such systems might be challenging, especially when nodes are comprised of CPUs and GPUs with different computational speeds. The framework dynamically schedules computations on the processing elements of the cluster according to a selected performance index, which is determined at run-time. The framework is extensible, as it allows easy integration of additional inverse problems.

We present parallel algorithms and data structures for three fundamental operations in Numerical Linear Algebra: (i) Gaussian and CountSketch random projections and their combination, (ii) computation of the Gram matrix, and (iii) computation of the squared row norms of the product of two matrices, with a special focus on “tall-and-skinny” matrices, which arise in many applications. We provide a detailed analysis of the ubiquitous CountSketch transform and its combination with Gaussian random projections, accounting for memory requirements, computational complexity and workload balancing. We also demonstrate how these results can be applied to column subset selection, least squares regression and leverage scores computation. These tools have been implemented in pylspack , a publicly available Python package 1 whose core is written in C++ and parallelized with OpenMP and that is compatible with standard matrix data structures of SciPy and NumPy. Extensive numerical experiments indicate that the proposed algorithms scale well and significantly outperform existing libraries for tall-and-skinny matrices.

PageRank is one of the most commonly used techniques for ranking nodes in a network. It is a special case of a family of link-based rankings, commonly referred to as functional rankings. Functional rankings are computed as power series of a stochastic matrix derived from the adjacency matrix of the graph. This general formulation of functional rankings enables their use in diverse applications, ranging from traditional search applications to identification of spam and outliers in networks. This paper presents a novel algorithmic (re)formulation of commonly used functional rankings, such as LinearRank, TotalRank and Generalized Hyperbolic Rank. These rankings can be approximated by finite series representations. We prove that polynomials of stochastic matrices can be expressed as products of Google matrices (matrices having the form used in Google's original PageRank formulation). Individual matrices in these products are parameterized by different damping factors. For this reason, we refer to our formulation as multidamping. We demonstrate that multidamping has a number of desirable characteristics: (i) for problems such as finding the highest ranked pages, multidamping admits extremely fast approximate solutions; (ii) multidamping provides an intuitive interpretation of existing functional rankings in terms of the surfing habits of model web users; (iii) multidamping provides a natural framework based on Monte Carlo type methods that have efficient parallel and distributed implementations. It also provides the basis for constructing new link-based rankings based on inhomogeneous products of Google matrices. We present algorithms for computing damping factors for existing functional rankings analytically and numerically. We validate various benefits of multidamping on a number of real datasets.

Jylab is a PSE architecture emphasizing portable computing over distributed platforms. It captures the idea of reusing some of the best open source software projects' functionality within the context of a single, net-aware, interactive environment. The original implementation of this idea resulted in a system built around a portable interpreter supported by a carefully selected suite of libraries spanning a comprehensive set of applications including scripting, numerical linear algebra, distributed/grid computing and Internet algorithmics. Because Jylab is a multicomponent PSE system, it is quite natural to base its implementation on a robust platform automating the management of complex stacks of software components, i.e. self-describing objects. The Eclipse platform meets this basic prerequisite, additionally providing many other interesting integration facilities, an extensive set of ready-to-use plug-ins and is also embraced by a vibrant community of users, developers and leading software companies. In this paper we describe the design and basic implementation of a flexible environment resulting from the integration of Jylab into Eclipse. To this effect, we survey relevant aspects of the rich Eclipse ecosystem as well as the Jylab approach to PSE construction. To illustrate our environment we present case studies from grid computing, neural network training and native libraries integration.

Jylab is a portable and flexible scientific computing system favoring extensibility. It provides users with a scripting language and a core set of libraries implementing numerical linear algebra routines, communication models, interactive visualization and computer algebra system capabilities. It thus enables the development of scientific applications involving numerics, graphics and symbolics over distributed computing platforms. It is enhanced with a collection of extension packages that support Grid computing and implement Web search engine and Web graph analysis frameworks. Building a multithreaded Internet algorithmics application in Jylab is fully presented.

We address the problem of building fast and effective text classification tools. We describe a "representatives methodology" related to feature extraction and illustrate its performance using as vehicles a centroid based method and a method based on clustered LSI that were recently proposed as useful tools for low rank matrix approximation and cost effective alternatives to LSI. The methodology is very flexible, providing the means for accelerating existing algorithms. It is also combined with kernel techniques to enable the analysis of data for which linear techniques are insufficient. Numerous classification examples indicate that the proposed technique is effective and efficient with an overall performance superior than existing linear and nonlinear LSI-based approaches.

We investigate a methodology for matrix approximation and IR. A central feature of these techniques is an initial clustering phase on the columns of the term-document matrix, followed by partial svd on the columns constituting each cluster. The extracted information is used to build effective low rank approximations to the original matrix as well as for IR. The algorithms can be expressed by means of rank reduction formulas. Experiments indicate that these methods can achieve good overall performance for matrix approximation and IR and compete well with existing schemes.

Given a matrix A, the computation of its pseudospectrum (A) is a far more expensive task than the computation of characteristics such as the condition number and the matrix spectrum. As research of the last 15 years has shown, however, the matrix pseudospectrum provides valuable information that is not included in other indicators. So, ask how to compute it eciently and build a tool that would facilitate engineers and scientists to make such analyses? In this paper we focus on parallel algorithms for computing pseudospectra. The most widely used algorithm for computing pseudospectra is embarassingly parallel; nevertheless, it is extremely costly and one cannot hope to achieve absolute high performance with it. We describe algorithms that have drastically improved performance while maintaining a high degree of large grain parallelism. We evaluate the eectiveness of these methods in the context of a MATLAB-based environment for parallel programming using MPI on small, o-the-shelf parallel systems. Keywords Pseudospectra, MPI, MATLAB, NOWs 1.

We present the design of the GFDL ocean circulation model as adapted for simulations of the Mediterranean basin for the Cedar multicluster architecture. The model simulates the basic aspects of large-scale, baroclinic ocean circulation, including treatment of irregular bottom topography. The data and computational mapping strategies and their effect on the design are discussed. The code was parameterized to offer several choices for data partitionings of the computational domain, for placement strategies for the data in the memory hierarchy, and for the number of clusters and processors used in the computational hierarchy of Cedar. The experiments and performance trends are discussed. Using four clusters and 32 processors the code demonstrates significant speedup compared to a single cluster and compared to a single processor. 1 Introduction The numerical modeling of ocean circulation is a task of great importance, both in its own right, as well as a component of climate studies. Num...

We propose new parallel algorithms for the solution of linear parabolic problems. The first of these methods is based on using polynomial approximation to the exponential. It does not require solving any linear systems and is highly parallelizable. The two other methods proposed are based on Padé and Chebyshev approximations to the matrix exponential. The parallelization of these methods is achieved by using partial fraction decomposition techniques to solve the resulting systems and thus offers the potential for increased time parallelism in time dependent problems. We also present experimental results from the Alliant FX/8 and the Cray Y-MP/832 vector multiprocessors.

A method, called Boundary Integral-based Domain Decomposition was recently proposed for the solution of Laplace's equation. The method is characterized by the complete decoupling of the problem domain into subdomains which is possible after integral equation based techniques are used for the calculation of the solution on the subdomain boundaries. We describe some theoretical and practical issues involved in the use of such methods on shared memory multiprocessors.