An Investigation into Spectral Sequencing using Graph

The construction of linear mesh layouts has found various applications, such as implicit mesh flltering and mesh streaming, where a variety of layout quality criteria, e.g., width and span, can be consid- ered. Similar linear sequencing problems have also been studied in the context of sparse matrix reordering and graph labeling, where width and span correspond to vertex separation and bandwidth, respectively. One of the best-known heuristics for generating width-minimizing orderings is spectral sequencing, which is

derived from the Fiedler vector. In terms of span however, other heuristics, such as the Cuthill-Mckee (CM) scheme, generally outperform spectral sequencing. In this paper, we study the general linear sequence generation as a problem of preserving graph dis- tances and propose to use for sequencing the subdominant eigenvector of a kernel (a–nity) matrix, deflned by graph distances and appropriately chosen transfer functions. The use of Laplacians can then be seen as a special case, where a step transfer function of unit width is applied. De- spite the non-sparsity of the kernel matrix we use, the sequences can be computed e–ciently for problems of large size through subsampling and eigenvector extrapolation. When applied to mesh layouts generation, we show experimentally that the sequences obtained using our algorithm outperform those derived from the Fiedler vector, in terms of spans, and those obtained from CM, in terms of widths and other important quality criteria. Therefore, in applications where several such quality criteria can in uence algorithm performance simultaneously, e.g., mesh streaming and implicit mesh flltering, the new mesh layouts could potentially provide a better trade-ofi. 1 Introduction The computation of linear mesh layouts is an instance of the general graph layout problem [1], where an optimal labeling or ordering of the vertices of a given graph is sought. Many optimization problems, from diverse flelds, can be 2 R. Liu, H. Zhang and O. van Kaick formulated as graph layout problems; these include sparse matrix reordering in numerical analysis [2{5], circuit layout in VLSI design [6], DNA sequencing in computational biology [7], archaeological dating, as well as ranking problems in geography [8] and information retrieval [9]. A variety of layout costs have been considered and most of them lead to NP-hard optimization problems [1]. The mesh layout problem is of interest since the application-based optimal sequencing of the mesh faces, vertices, or higher-order entities, e.g., nodes in a multiresolution or bounding volume hierarchy [10], can lead to superior per- formance for rendering [11,10] and geometry processing [10,12{14], typically without modifying the run-time algorithm. Such reordering can also make large mesh data more streamable [15] and facilitate stream processing, e.g., in mesh simpliflcation [16]. Layout costs relevant to these applications include width and span [15] for mesh streaming, matrix proflle, workbound, and bandwidth [2,4,3] for solution of sparse linear systems related to mesh processing, e.g., in implicit mesh fairing [13,14], as well...

Website: www.cs.sfu.ca | Filesize: -
No of Page(s): 19
Download An Investigation into Spectral Sequencing using Graph ... - CiteSeer.pdf