In this paper, we develop two fast implicit difference schemes for solving a class of variable‐coefficient time–space fractional diffusion equations with integral fractional Laplacian (IFL). The proposed schemes utilize the graded
Fast Stencil Computations using Fast Fourier Transforms
Stencil computations are widely used to simulate the change of state of physical systems across a multidimensional grid over multiple timesteps. The state-of-the-art techniques in this area fall into three groups: cache-aware tiled looping algorithms, cache-oblivious divide-and-conquer trapezoidal algorithms, and Krylov subspace methods.
In this paper, we present two efficient parallel algorithms for performing linear stencil computations. Current direct solvers in this domain are computationally inefficient, and Krylov methods require manual labor and mathematical training. We solve these problems for linear stencils by using DFT preconditioning on a Krylov method to achieve a direct solver which is both fast and general. Indeed, while all currently available algorithms for solving general linear stencils perform Θ(NT) work, where N is the size of the spatial grid and T is the number of timesteps, our algorithms perform o(NT) work.
To the best of our knowledge, we give the first algorithms that use fast Fourier transforms to compute final grid data by evolving the initial data for many timesteps at once. Our algorithms handle both periodic and aperiodic boundary conditions, and achieve polynomially better performance bounds (i.e., computational complexity and parallel runtime) than all other existing solutions.
Initial experimental results show that implementations of our algorithms that evolve grids of roughly 10^7 cells for around 10^5 timesteps run orders of magnitude faster than state-of-the-art implementations for periodic stencil problems, and 1.3× to 8.5× faster for aperiodic stencil problems.
more »
« less
- NSF-PAR ID:
- 10298518
- Date Published:
- Journal Name:
- Annual ACM Symposium on Parallelism in Algorithms and Architectures
- ISSN:
- 1548-6109
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
L 1M ‐matrix analysis, which is from the spatial discretized matrix of IFL. Moreover, the proposed schemes use the fast sum‐of‐exponential approximation and Toeplitz matrix algorithms to reduce the computational cost for the nonlocal property of time and space fractional derivatives, respectively. The fast schemes greatly reduce the computational work of solving the discretized linear systems from by a direct solver to per preconditioned Krylov subspace iteration and a memory requirement from𝒪 (M N 2)𝒪 (N N e x p )N and( are the number of spatial and temporal grid nodes, respectively. The spectrum of preconditioned matrix is also given for ensuring the acceleration benefit of circulant preconditioners. Finally, numerical results are presented to show the utility of the proposed methods.N e x p ≪)M -
In the era of big data and cloud computing, large amounts of data are generated from user applications and need to be processed in the datacenter. Data-parallel computing frameworks, such as Apache Spark, are widely used to perform such data processing at scale. Specifically, Spark leverages distributed memory to cache the intermediate results, represented as Resilient Distributed Datasets (RDDs). This gives Spark an advantage over other parallel frameworks for implementations of iterative machine learning and data mining algorithms, by avoiding repeated computation or hard disk accesses to retrieve RDDs. By default, caching decisions are left at the programmer’s discretion, and the LRU policy is used for evicting RDDs when the cache is full. However, when the objective is to minimize total work, LRU is woefully inadequate, leading to arbitrarily suboptimal caching decisions. In this paper, we design an algorithm for multi-stage big data processing platforms to adaptively determine and cache the most valuable intermediate datasets that can be reused in the future. Our solution automates the decision of which RDDs to cache: this amounts to identifying nodes in a direct acyclic graph (DAG) representing computations whose outputs should persist in the memory. Our experiment results show that our proposed cache optimization solution can improve the performance of machine learning applications on Spark decreasing the total work to recompute RDDs by 12%.more » « less
-
null (Ed.)In this paper we describe a new parallel algorithm called Fast Adaptive Sequencing Technique (FAST) for maximizing a monotone submodular function under a cardinality constraint k. This algorithm achieves the optimal 1-1/e approximation guarantee and is orders of magnitude faster than the state-of-the-art on a variety of experiments over real-world data sets. Following recent work by Balkanski & Singer (2018a), there has been a great deal of research on algorithms whose theoretical parallel runtime is exponentially faster than algorithms used for sub- modular maximization over the past 40 years. However, while these new algorithms are fast in terms of asymptotic worst-case guarantees, it is computationally infeasible to use them in practice even on small data sets because the number of rounds and queries they require depend on large constants and high-degree polynomials in terms of precision and confidence. The design principles behind the FAST algorithm we present here are a significant departure from those of recent theoretically fast algorithms. Rather than optimize for asymptotic theoretical guarantees, the design of FAST introduces several new techniques that achieve remarkable practical and theoretical parallel runtimes. The approximation guarantee obtained by FAST is arbitrarily close to 1-1/e, and its asymptotic parallel runtime (adaptivity) is O(log(n) log2(log k)) using O(n log log(k)) total queries. We show that FAST is orders of magnitude faster than any algorithm for submodular maximization we are aware of, including hyper-optimized parallel versions of state-of-the-art serial algorithms, by running experiments on large data sets.more » « less
-
Counting the frequency of subgraphs in large networks is a classic research question that reveals the underlying substructures of these networks for important applications. However, subgraph counting is a challenging problem, even for subgraph sizes as small as five, due to the combinatorial explosion in the number of possible occurrences. This article focuses on the five-cycle, which is an important special case of five-vertex subgraph counting and one of the most difficult to count efficiently. We design two new parallel five-cycle counting algorithms and prove that they are work efficient and achieve polylogarithmic span. Both algorithms are based on computing low out-degree orientations, which enables the efficient computation of directed two-paths and three-paths, and the algorithms differ in the ways in which they use this orientation to eliminate double-counting. Additionally, we present new parallel algorithms for obtaining unbiased estimates of five-cycle counts using graph sparsification. We develop fast multicore implementations of the algorithms and propose a work scheduling optimization to improve their performance. Our experiments on a variety of real-world graphs using a 36-core machine with two-way hyper-threading show that our best exact parallel algorithm achieves 10–46× self-relative speedup, outperforms our serial benchmarks by 10–32×, and outperforms the previous state-of-the-art serial algorithm by up to 818×. Our best approximate algorithm, for a reasonable probability parameter, achieves up to 20× self-relative speedup and is able to approximate five-cycle counts 9–189× faster than our best exact algorithm, with between 0.52% and 11.77% error.more » « less
-
Purpose The purpose of this paper is as follows: to significantly reduce the computation time (by a factor of 1,000 and more) compared to known numerical techniques for real-world problems with complex interfaces; and to simplify the solution by using trivial unfitted Cartesian meshes (no need in complicated mesh generators for complex geometry). Design/methodology/approach This study extends the recently developed optimal local truncation error method (OLTEM) for the Poisson equation with constant coefficients to a much more general case of discontinuous coefficients that can be applied to domains with different material properties (e.g. different inclusions, multi-material structural components, etc.). This study develops OLTEM using compact 9-point and 25-point stencils that are similar to those for linear and quadratic finite elements. In contrast to finite elements and other known numerical techniques for interface problems with conformed and unfitted meshes, OLTEM with 9-point and 25-point stencils and unfitted Cartesian meshes provides the 3-rd and 11-th order of accuracy for irregular interfaces, respectively; i.e. a huge increase in accuracy by eight orders for the new 'quadratic' elements compared to known techniques at similar computational costs. There are no unknowns on interfaces between different materials; the structure of the global discrete system is the same for homogeneous and heterogeneous materials (the difference in the values of the stencil coefficients). The calculation of the unknown stencil coefficients is based on the minimization of the local truncation error of the stencil equations and yields the optimal order of accuracy of OLTEM at a given stencil width. The numerical results with irregular interfaces show that at the same number of degrees of freedom, OLTEM with the 9-points stencils is even more accurate than the 4-th order finite elements; OLTEM with the 25-points stencils is much more accurate than the 7-th order finite elements with much wider stencils and conformed meshes. Findings The significant increase in accuracy for OLTEM by one order for 'linear' elements and by 8 orders for 'quadratic' elements compared to that for known techniques. This will lead to a huge reduction in the computation time for the problems with complex irregular interfaces. The use of trivial unfitted Cartesian meshes significantly simplifies the solution and reduces the time for the data preparation (no need in complicated mesh generators for complex geometry). Originality/value It has been never seen in the literature such a huge increase in accuracy for the proposed technique compared to existing methods. Due to a high accuracy, the proposed technique will allow the direct solution of multiscale problems without the scale separation.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
