Cache-Oblivious Algorithms

DOI10.1145/2071379.2071383zbMath1295.68236OpenAlexW2052196304MaRDI 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

zbMATH Keywords

sortingfast Fourier transformcachingmatrix multiplicationcache-obliviousmatrix transposeI/O complexity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Numerical methods for discrete and fast Fourier transforms (65T50) Mathematical problems of computer architecture (68M07) Numerical algorithms for computer arithmetic, etc. (65Y04)

Related Items

Packing a Knapsack of Unknown Capacity, Scientific computations on multi-core systems using different programming frameworks, On Memory Traffic and Optimisations for Low-order Finite Element Assembly Algorithms on Multi-core CPUs, Cache Oblivious Minimum Cut, Cache-Oblivious Iterated Predecessor Queries via Range Coalescing, Sorting and Permuting without Bank Conflicts on GPUs, I/O-Efficient Similarity Join, Space-Efficient Frameworks for Top- k String Retrieval, Implicit \(B\)-trees: A new data structure for the dictionary problem, I/O-efficient similarity join, Array Layouts for Comparison-Based Searching, Kings, Name Days, Lazy Servants and Magic, On the weak prefix-search 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, Unnamed Item, Pebbling Game and Alternative Basis for High Performance Matrix Multiplication, Oblivious algorithms for multicores and networks of processors, I/O efficient dynamic data structures for longest prefix queries, Cache oblivious algorithms for the RMQ and the RMSQ problems, Out-of-core computations of high-resolution level sets by means of code transformation, Minimizing I/Os in Out-of-Core Task Tree Scheduling, External-memory sorting with comparison errors, Optimal cache-oblivious mesh layouts, The cost of cache-oblivious searching, I/O-efficient data structures for non-overlapping indexing, Cache-Oblivious Red-Blue Line Segment Intersection, I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions, An approach to multicore parallelism using functional programming: a case study based on Presburger arithmetic, On the limits of cache-oblivious rational permutations, On the importance of cache tuning in a cache-aware algorithm: a case study, Introduction to Communication Avoiding Algorithms for Direct Methods of Factorization in Linear Algebra, An algorithm for the sequence alignment with gap penalty problem using multiway divide-and-conquer and matrix transposition, On the Weak Prefix-Search Problem, Resilient dynamic programming, On sorting, heaps, and minimum spanning trees, Unnamed Item, Cache-oblivious index for approximate string matching, Basic Polynomial Algebra Subprograms, An empirical study of cache-oblivious polygon indecomposability testing, Cache-oblivious selection in sorted \(X+Y\) matrices, Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions, The worst page-replacement policy, Unnamed Item, Cache oblivious matrix multiplication using an element ordering based on a Peano curve, 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, On the Limits of Cache-Oblivious Matrix Transposition, 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, Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis, Masking patterns in sequences: A new class of motif discovery with don't cares, The cache complexity of multithreaded cache oblivious algorithms, A Cache-Optimal Alternative to the Unidirectional Hierarchization Algorithm, Cache-oblivious R-trees, Design and Engineering of External Memory Traversal Algorithms for General Graphs, On a Model of Virtual Address Translation, Via Detours to I/O-Efficient Shortest Paths, An Efficient Multicore Implementation of a Novel HSS-Structured Multifrontal Solver Using Randomized Sampling, Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees, A Survey on Priority Queues, Unnamed Item, RAM-Efficient External Memory Sorting, The basic polynomial algebra subprograms, Non-Overlapping Indexing - Cache Obliviously, Space-efficient substring occurrence estimation