SFCGen swMATH ID: 852 Software Authors: Jin, Guohua; Mellor-Crummey, John Description: SFCGen: A framework for efficient generation of multi-dimensional space-filling curves by recursion. Because they are continuous and self-similar, space-filling curves have been widely used in mathematics to transform multi-dimensional problems into one-dimensional forms. For scientific applications, reordering computation by certain space-filling curves can significantly improve data reuse because of the locality properties of these curves. However, when space-filling curves are used in programs for reordering data, traversal or indexing of the curves must be efficient.par To address this problem, we present the table-driven framework SFCGen to efficiently generate multi-dimensional space-filling curves on the fly. The framework is general and easy enough to be used in any application that can be partitioned recursively in multiple dimensions. We describe a movement specification table, a universal turtle algorithm to enumerate points along a space-filling curve, a table-based indexing algorithm to transform coordinates of a point into its position along the curve and an algorithm to pregenerate the table automatically.par As examples, we show how high-dimensional Hilbert, Morton, and Peano curves and a two-dimensional Sierpiński curve can be generated with our algorithms. We present performance results for Hilbert, Morton, and Peano curves and compare the efficiency of our curve generation algorithm with the most recent work on generating Hilbert curves. Our experimental results on three modern microprocessor-based platforms show that SFCGen performs up to 63 Homepage: http://dl.acm.org/citation.cfm?doid=1055531.1055537 Keywords: multi-dimensional space-filling curves; universal turtle algorithm; table-based indexing algorithm; Peano curves; performance; Hilbert curves; Morton curves; numerical examples; Sierpi\'nski curve Related Software: Algorithm 781; Intel TBB; AMRCLAW; Peano; GEOCLAW; METIS; Globus Toolkit; Chord Cited in: 5 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year SFCGen: A framework for efficient generation of multi-dimensional space-filling curves by recursion. Zbl 1073.65017Jin, Guohua; Mellor-Crummey, John 2005 all top 5 Cited by 13 Authors 1 Bungartz, Hans-Joachim 1 Chopin, Nicolas 1 Gerber, Mathieu 1 Hamilton, Chris H. 1 He, Zhijian 1 Jin, Guohua 1 Konrad, Christian 1 Mellor-Crummey, John 1 Neckel, Tobias 1 Niederreiter, Harald 1 Rau-Chaplin, Andrew 1 Schreiber, Martin 1 Schretter, Colas Cited in 4 Serials 1 Information Processing Letters 1 ACM Transactions on Mathematical Software 1 Parallel Computing 1 SIAM Journal on Scientific Computing all top 5 Cited in 6 Fields 3 Numerical analysis (65-XX) 2 Computer science (68-XX) 1 Number theory (11-XX) 1 Approximations and expansions (41-XX) 1 Fluid mechanics (76-XX) 1 Operations research, mathematical programming (90-XX) Citations by Year