The truncated singular value decomposition and its various tensor generalizations have long offered a simple and practical mechanism for compressing data stored in 2D or higherorder tensors. While the resulting low-rank approximations provide strong guarantees on the quality of the resulting reconstruction, they do not always provide sufficient compression as needed by the increasingly large scientific data volumes being produced in large-scale spatio-temporal simulations. In this paper, we introduce a second-stage compression where the singular vectors themselves are further compressed, adding a multiplicative effect on the overall compression ratios achieved. The intuition of this second-stage compression is that singular vectors associated with smaller singular values can be compressed using lower accuracies without compromising the overall accuracy targeted in the compression. Specifically, we show that if the singular vectors are compressed with an accuracy inversely proportional to their singular values, the overall accuracy reached can be readily controlled. We show the effectiveness of the resulting algorithm on sample representative datasets from climate, weather, and computational fluid dynamics, where the proposed algorithm achieves higher compression ratios than other state-of-the-art algorithms for the same target root mean square accuracies. The strength of the method appears to lie in its combination of global feature-level SVD-based compression in the first stage and local entry-level interpolation-guided compression in the second stage, leveraging the complementary strengths of both approaches in a unified pipeline.

Hierarchical matrices are space- and time-efficient representations of dense matrices that exploit the low-rank structure of matrix blocks at different levels of granularity. The hierarchically low-rank block partitioning produces representations that can be stored and operated on in near-linear complexity instead of the usual polynomial complexity of dense matrices. In this article, we present high-performance implementations of matrix vector multiplication and compression operations for the H 2 variant of hierarchical matrices on GPUs. The H 2 variant exploits, in addition to the hierarchical block partitioning, hierarchical bases for the block representations and results in a scheme that requires only O ( n ) storage and O ( n ) complexity for the mat-vec and compression kernels. These two operations are at the core of algebraic operations for hierarchical matrices, the mat-vec being a ubiquitous operation in numerical algorithms while compression/recompression represents a key building block for other algebraic operations, which require periodic recompression during execution. The difficulties in developing efficient GPU algorithms come primarily from the irregular tree data structures that underlie the hierarchical representations, and the key to performance is to recast the computations on flattened trees in ways that allow batched linear algebra operations to be performed. This requires marshaling the irregularly laid out data in a way that allows them to be used by the batched routines. Marshaling operations only involve pointer arithmetic with no data movement and as a result have minimal overhead. Our numerical results on covariance matrices from 2D and 3D problems from spatial statistics show the high efficiency our routines achieve over 550GB/s for the bandwidth-limited matrix-vector operation and over 850GFLOPS/s in sustained performance for the compression operation on the P100 Pascal GPU.

We present Accelerated Cyclic Reduction (ACR), a distributed-memory fast solver for rank-compressible block tridiagonal linear systems arising from the discretization of elliptic operators , developed here for three dimensions . Algorithmic synergies between Cyclic Reduction and hierarchical matrix arithmetic operations result in a solver that has O ( k N log N ( log N + k 2 ) ) arithmetic complexity and O ( k N log N ) memory footprint , where N is the number of degrees of freedom and k is the rank of a block in the hierarchical approximation , and which exhibits substantial concurrency. We provide a baseline for performance and applicability by comparing with the multifrontal method with and without hierarchical semi-separable matrices, with algebraic multigrid and with the classic cyclic reduction method. Over a set of large-scale elliptic systems with features of nonsymmetry and indefiniteness, the robustness of the direct solvers extends beyond that of the multigrid solver, and relative to the multifrontal approach ACR has lower or comparable execution time and size of the factors, with substantially lower numerical ranks . ACR exhibits good strong and weak scaling in a distributed context and, as with any direct solver, is advantageous for problems that require the solution of multiple right-hand sides. Numerical experiments show that the rank k patterns are of O (1) for the Poisson equation and of O ( n ) for the indefinite Helmholtz equation. The solver is ideal in situations where low-accuracy solutions are sufficient, or otherwise as a preconditioner within an iterative method.

3G UMTS networks are being widely deployed by several cellular operators worldwide that already have existing GSM networks. In this paper, we model the problem of GSM/UMTS co-siting as a nested mixed integer optimization problem which takes as input an area of interest with existing GSM sites and obtains as output the optimal number and locations of UMTS sites to be deployed (new and co-sited with GSM sites) in order to optimize target objectives. The goal is to minimize the cost of UMTS network deployment by reusing as many existing GSM sites as possible while guaranteeing that every cell is covering a target capacity load which is a percentage of the downlink pole capacity. We propose an algorithm taking into account both integer and continuous variables to solve the formulated optimization problem as a function of the user distribution and the existing fixed GSM site locations. Results for different scenarios show that it is optimal to reuse a subset of the existing GSM sites in addition to deploying new UMTS sites.

The ability to cut through meshes in real-time is an essential ingredient in a number of practical interactive simulations. Surgical simulation, cloth design, clay sculpting and many other related VR applications require the ability to introduce arbitrary discontinuities through models to separate, reposition, and reshape various pieces of the model as needed for the target application. In addition, in order to provide the necessary realism for these applications, model deformations must be computed from an underlying physically-based model--most commonly a continuum-based finite element model.

General haptic interaction with solid models requires an underlying physically-based model that can generate, in real-time, the forces and deformations to be rendered as a result of user interaction. In order to allow for a rich set of interactions, the physical model must support real-time topological modifications including the embedding of new elements in the model, and the introduction of cuts in the geometry. In this paper, we describe and demonstrate a physically-based framework for real-time interaction with 3D solid models discretized by finite elements. We present a model formulation that allows for fast progressive updates to be used in modeling the addition of new elements as well as dynamic inter- and intra-element changes in model connectivity. Our motivating applications have been in the area of open suturing simulations where cutting through skin and tissue, undermining skin to separate it from the underlying soft tissue, addition of sutures to close wounds, and manipulation using multiple surgical instruments simultaneously, are all tasks that must be supported. We show a new surgical simulator we recently developed to demonstrate the framework.

Real-time finite element (FE) analysis can be used to represent complex deformable geometries in virtual environments. The need for accurate surgical simulation has spurred the development of many of the new real-time FE methodologies that enable haptic support and real-time deformation. These techniques are computationally intensive and it has proved to be a challenge to achieve the high modeling resolutions required to accurately represent complex anatomies. The authors present a new real-time methodology based on linear FE analysis that is appropriate for a wide range of surgical simulation applications. A methodology is proposed that is characterized by high model resolution, low preprocessing time, unrestricted multipoint surface contact, and adjustable boundary conditions. These features make the method ideal for modeling suturing, which is an element common to almost every surgical procedure. This paper describes constraints in the context of a Suturing Simulator currently being developed by the authors.

This paper presents a framework for autonomous robots that reason from range data. We argue for spatial reasoning as a basic cognition mode for robots operating in unpredictable work environments and present a three-level architecture for modeling and planning from range data. Two implementations, robotic excavation with sonar ranging and mine navigation with laser ranging, illustrate the techniques and provide two experiences to evaluate the architecture.