Cache-Oblivious Algorithms
From MaRDI portal
Publication:3189045
DOI10.1145/2071379.2071383zbMath1295.68236MaRDI QIDQ3189045
Matteo Frigo, Charles E. Leiserson, Sridhar Ramachandran, Harald Prokop
Publication date: 9 September 2014
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2071379.2071383
sorting; fast Fourier transform; caching; matrix multiplication; cache-oblivious; matrix transpose; I/O complexity
68W40: Analysis of algorithms
68P10: Searching and sorting
65T50: Numerical methods for discrete and fast Fourier transforms
68M07: Mathematical problems of computer architecture
65Y04: Numerical algorithms for computer arithmetic, etc.
Related Items
I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions, Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis, Efficient implementation of the Pivot algorithm for self-avoiding walks, A note on the \(O(n)\)-storage implementation of the GKO algorithm and its adaptation to Trummer-like matrices, Out-of-core computations of high-resolution level sets by means of code transformation, Cache-oblivious index for approximate string matching, Implicit \(B\)-trees: A new data structure for the dictionary problem, The cache-oblivious Gaussian elimination paradigm: Theoretical framework, parallelization and Experimental evaluation, Optimal sparse matrix dense vector multiplication in the I/O-model, ISB-tree: A new indexing scheme with efficient expected behaviour, Cache oblivious algorithms for the RMQ and the RMSQ problems, Optimal cache-oblivious mesh layouts, The cost of cache-oblivious searching, Masking patterns in sequences: A new class of motif discovery with don't cares, The cache complexity of multithreaded cache oblivious algorithms, On the limits of cache-oblivious rational permutations, On sorting, heaps, and minimum spanning trees, An empirical study of cache-oblivious polygon indecomposability testing, Cache-oblivious selection in sorted \(X+Y\) matrices, Assembling approximately optimal binary search trees efficiently using arithmetics, Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection, A general approach for cache-oblivious range reporting and approximate range counting, Cache-oblivious R-trees, Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions, The worst page-replacement policy, On the importance of cache tuning in a cache-aware algorithm: a case study, Cache oblivious matrix multiplication using an element ordering based on a Peano curve, On the Weak Prefix-Search Problem, Cache-Oblivious Red-Blue Line Segment Intersection, On the Limits of Cache-Oblivious Matrix Transposition, Design and Engineering of External Memory Traversal Algorithms for General Graphs, Via Detours to I/O-Efficient Shortest Paths
