Optimal cache-oblivious mesh layouts

DOI10.1007/s00224-009-9242-2zbMath1211.68279arXiv0705.1033MaRDI QIDQ633762

Kebin Wang, Michael A. Bender, Shang-Hua Teng, Bradley C. Kuszmaul

Publication date: 30 March 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0705.1033

zbMATH Keywords

decomposition tree; cache-oblivious; fully-balanced decomposition tree; geometric separator; mesh layout; relax-balanced decomposition tree

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

Uses Software

• ATLAS
• OSKI
• Cilk
• Chaco

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal sparse matrix dense vector multiplication in the I/O-model
• A framework for solving VLSI graph layout problems
• Blocking for external graph searching
• Cache-Oblivious Algorithms
• Bisection of Circle Colorings
• Engineering a cache-oblivious sorting algorithm
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• Locality of Reference in LU Decomposition with Partial Pivoting
• Geometric Separators for Finite-Element Meshes
• Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation
• UNSTRUCTURED MESH GENERATION: THEORY, PRACTICE, AND PERSPECTIVES
• Algorithm Theory - SWAT 2004
• An Optimal Cache‐Oblivious Priority Queue and Its Application to Graph Algorithms
• Automata, Languages and Programming
• A fast algorithm for particle simulations
• Min-max-boundary domain decomposition