Linear algebraic representation for topological structures

Highlights

• A proper mathematical model for all topological structures is a (co)chain complex.

• We propose a linear algebraic representation (LAR) scheme for representing such complexes.

• The LAR scheme is fully implemented using sparse matrices.

• The LAR scheme provides efficient support for topological queries and constructions.

Abstract

With increased complexity of geometric data, topological models play an increasingly important role beyond boundary representations, assemblies, finite elements, image processing, and other traditional modeling applications. While many graph- and index-based data structures have been proposed, no standard representation has emerged as of now. Furthermore, such representations typically do not deal with representations of mappings and functions and do not scale to support parallel processing, open source, and client-based architectures. We advocate that a proper mathematical model for all topological structures is a (co)chain complex: a sequence of (co)chain spaces and (co)boundary mappings. This in turn implies all topological structures may be represented by a collection of sparse matrices. We propose a Linear Algebraic Representation (LAR) scheme for mod 2 (co)chain complexes using CSR matrices and show that it supports a variety of topological computations using standard matrix algebra, without any overhead in space or running time. A full open source implementation of LAR is available and is being used for a variety of applications.

Introduction

Present-day computational problems in science and technology must deal with increasingly complex geometric information and applications. The complexity of geometric information stems from a dramatic increase in size, diversity, and complexity of geometric data: point clouds, boundary meshes, NURBs representations, finite element meshes, CT scans, and so on. The complexity of applications is apparent in increasingly complicated semantics, usually expressed in terms of incidences and relations involving geometric data: large-scale assemblies, topology of microstructure, image segmentation, multi-physics simulation, to name a few. Emerging applications require the convergence of shape synthesis and analysis from computer graphics, computer imaging, and computer-aided geometric design, with discrete meshing of domains used for physical simulations. The goals of unification, scalability, and massively parallel distributed computing call for rethinking of the foundations of geometric and topological computing.

The evolution of 3D geometric representations can be generally understood in terms of graph-based data structures representing one of several possible cell complexes partitioning either the boundary or the interior of the represented model. A variety of assumptions about cell complexes and graph representations make standardization difficult, complicate the issues of data exchange and transfer, and lead to the proliferation of incompatible algorithms. Graph-based structures are difficult to parallelize: e.g. boundary representation algorithms are dominated by graph searching algorithms (boundary traversals) that tend to force serial processing. In short, the specialized data structures based on cell complexes, that have driven the evolutionary development of the field, are no longer adequate for dealing with the emerging challenges and opportunities in geometric computing.

We observe that all types of cell complexes and functions over cell complexes are properly represented by a (co)chain complex, that captures all combinatorial relationships of interest in solid and physical modeling formally and unambiguously. Based on classical results from algebraic topology techniques, we show that a (co)chain complex and all associated combinatorial operations are readily represented using standard techniques from linear algebra, giving rise to a Linear Algebraic Representation (LAR) scheme. In this paper, we focus specifically on mod 2 (co)chain complexes because they are sufficient for many solid modeling applications  [1]. In particular, we describe a fully implemented LAR data structure and algorithms using compressed sparse row (CSR) matrices that introduce no computational overhead and are asymptotically as efficient as (and usually better than) many other popular topological data structures. Our presentation will focus on chain complexes and operations. The extension to cochain complexes is straightforward because the two are isomorphic. For example, it is well known that boundary and coboundary matrices are transposes of each other.

The literature on representation schemes in solid modeling started with the foundational paper  [1], where a mathematical framework for the important aspects of computer representations of solids was introduced. The ground-breaking paper  [2] had previously supplied the first but already efficient boundary representation scheme. It also introduced Euler operators, elementary operations for step-wise building well-formed polyhedra, using atomic software actions satisfying the Euler–Poincaré formula at each stage.

The Quad-Edge data structure, providing efficient primitives for planar subdivisions and Voronoi diagrams, was proposed in  [3], and is still largely used in computational geometry algorithms and in geometric libraries. Variations of the radial-edge non-manifold representation by  [4] have been embodied in almost every commercial CAD system that uses a non-manifold boundary representation. The Cell–Tuple structure  [5] was introduced as a simple, uniform representation of finite and regular CW-complexes over subdivided $d$-manifolds.

More general set-theoretic and topological operators were provided by  [6] to represent inhomogeneous objects, building upon the Selective Geometric Complex (SGC), a superset of CW-complexes allowing for cells non homeomorphic to open balls, proposed to handle dimension-independent models of point sets with internal structures and incomplete boundaries. A dimension-independent generalization of simplicial schemes, and various operators and algorithms were discussed by  [7]. The foundational ideas underlying these and other representations are reviewed in  [8], pointing out that solid modeling was conceived as a universal technology for developing engineering languages and systems with guaranteed geometric validity.

Despite the tremendous amount of research done and the progress made, most modern industrial systems still follow the basic approach established twenty years ago, centered on boundary representations, graphs, and non-manifold data structures represented using complex and inefficient (usually redundant) pointer structures. Computations in such systems, without preprocessing, usually rely on sequential “traversal” (graph or boundary) algorithms that depend on specific pointer structures, and do not readily scale. For example, handling large 3D unstructured meshes becomes problematic, but the situation is much more challenging for other higher-dimensional topological structures.

More recently, the geometric and physical modeling fields started moving towards computing with functions defined over more general cellular decompositions  [9], [10] and direct integration between geometry and physics  [11], [12], [13], [14]. These latest developments provided the motivation for the present paper; in particular, we will draw heavily on the ideas, concepts, and definitions in  [12] and  [13] to propose a new linear-algebraic approach to representing and computing with topological structures.