Tags: algorithms

More tags

Description

Whether you're simulating the electronic structure of a carbon nanotube or the strain within an automobile part, the calculations usually boil down to a simple matrix equation, Ax = f. The faster you can fill the matrix A with the coefficients for your partial differential equation (PDE), and the faster you can solve for the vector x given a forcing function f, the faster you have your overall solution. Things get interesting when the matrix A is too large to fit in the memory available on one machine, or when the coefficients in A cause the matrix to be ill-conditioned.

Many different algorithms have been developed to map a PDE onto a matrix, to pre-condition the matrix to a better form, and to solve the matrix with blinding speed. Different algorithms usually exploit some property of the matrix, such as symmetry, to reduce either memory requirements or solution speed or both.

Learn more about algorithms from the many resources on this site, listed below.

Online Presentations (21-40 of 115)

  1. ECE 695NS Lecture 2: Computability and NP-hardness

    Online Presentations | 13 Jan 2017 | Contributor(s):: Peter Bermel

    Outline:OverviewDefinitionsComputing MachinesChurch-Turing ThesisPolynomial Time (Class P)Class NPNon-deterministic Turing machinesReducibilityCook-Levin theoremCoping with NP Hardness

  2. Jupyter Notebooks for Scientific Programming

    Online Presentations | 06 Jan 2017 | Contributor(s):: Martin Hunt

    An overview of using Jupyter Notebooks for conveying scientific information.

  3. Machine learned approximations to Density Functional Theory Hamiltonians - Towards High-Throughput Screening of Electronic Structure and Transport in Materials

    Online Presentations | 13 Dec 2016 | Contributor(s):: Ganesh Krishna Hegde

    We present results from our recent work on direct machine learning of DFT Hamiltonians. We show that approximating DFT Hamiltonians accurately by direct learning is feasible and compare them to existing semi-empirical approaches to the problem. The technique we have proposed requires little...

  4. High Accuracy Atomic Force Microscope with Self-Optimizing Scan Control

    Online Presentations | 19 Sep 2016 | Contributor(s):: Ryan (Young-kook) Yoo

    Atomic force microscope (AFM) is a very useful instrument in characterizing nanoscale features, However, the original AFM design, based on piezo-tube scanner, had slow response and non-orthogonal behavior, inadequate to address the metrology needs of industrial applications: accuracy,...

  5. Memory-Efficient Particle Annihilation Algorithm for Wigner Monte Carlo Simulations

    Online Presentations | 10 Feb 2016 | Contributor(s):: Paul Ellinghaus

    IWCE 2015 presentation. The Wigner Monte Carlo solver, using the signed-particle method, is based on the generation and annihilation of numerical particles. The memory demands of the annihilation algorithm can become exorbitant, if a high spatial resolution is used, because the entire discretized...

  6. Data-Centric Models for Multilevel Algorithms

    Online Presentations | 07 Feb 2016 | Contributor(s):: Samuel Guiterrez

    Today, computational scientists must contend with a diverse set of supercomputer architectures that are capable of exposing unprecedented levels of parallelism and complexity. Effectively placing, moving, and operating on data residing in complex distributed memory hierarchies is quickly becoming...

  7. New FOSLS Formulation of Nonlinear Stokes Flow for Glaciers

    Online Presentations | 07 Feb 2016 | Contributor(s):: Jeffrey Allen

    This talk describes two First-order System Least-squares (FOSLS) formulations of the nonlinear Stokes flow used to model glaciers and ice sheets. The first is a Stress formulation and the second a Stress-Vorticity formulation. Both use fluidity, which is the reciprocal of viscosity and avoid the...

  8. Non-Blocking Conjugate Gradient Methods for Extreme Scale Computing

    Online Presentations | 07 Feb 2016 | Contributor(s):: Paul Eller

    Many scientific and engineering applications use Krylov subspace methods to solve large systems of linear equations. For extreme scale parallel computing systems, the dot products in these methods (implemented using allreduce operations in MPI) can limit performance because they are a...

  9. Range Decomposition: A Low Communication Algorithm for Solving PDEs on Massively Parallel Machines

    Online Presentations | 07 Feb 2016 | Contributor(s):: Tom Manteuffel

    The Range Decomposition (RD) algorithm uses nested iteration and adaptive mesh refinement locally before performing a global communication step. Only several such steps are observed to be necessary before reaching a solution within a small multiple of discretization error. The target application...

  10. A Scalable Algorithm for Inverse Medium Problems with Multiple Sources

    Online Presentations | 04 Feb 2016 | Contributor(s):: Keith Kelly

    We consider the problem of acoustic scattering as described by the free-space, time-harmonic scalar wave equation given by   (0.1)   along with radiation boundary conditions. Here, is a point in , is the source term, and is the wavenumber. Our formulation is based on potential theory....

  11. A Massively Parallel Semicoarsening Multigrid for 3D Reservoir Simulation on Multi-core and Multi-GPU Architectures

    Online Presentations | 04 Feb 2016 | Contributor(s):: Abdulrahman Manea

    In this work, we have designed and implemented a massively parallel version of the Semicoarsening Black Box Multigrid Solver [1], which is capable of handling highly heterogeneous and anisotropic 3D reservoirs, on a parallel architecture with multiple GPU’s. For comparison purposes, the...

  12. Understanding the Propagation of Silent Data Corruption in Algebraic Multigrid

    Online Presentations | 04 Feb 2016 | Contributor(s):: Jon Calhoun

    Sparse linear solvers from a fundamental kernel in high performance computing (HPC). Exascale systems are expected to be more complex than systems of today being composed of thousands of heterogeneous processing elements that operate at near-threshold-voltage to meet power constraints. The...

  13. A Performance Comparison of Algebraic Multigrid Preconditioners on GPUs and MIC

    Online Presentations | 04 Feb 2016 | Contributor(s):: Karl Rupp

    Algebraic multigrid (AMG) preconditioners for accelerators such as graphics processing units (GPUs) and Intel's many-integrated core (MIC) architecture typically require a careful, problem-dependent trade-off between efficient hardware use, robustness, and convergence rate in order to...

  14. Geometric Multigrid for MHD Simulations with Nedelec Finite Elements on Tetrahedral Grids

    Online Presentations | 04 Feb 2016 | Contributor(s):: Chris Hansen

    The Magneto-HydroDynamic (MHD) model is used extensively to simulate macroscopic plasma dynamics in Magnetic Confinement Fusion (MCF) devices. In these simulations, the span of time scales from fast wave dynamics to the desired evolution of equilibrium due to transport processes is large,...

  15. Parallel Multigrid Preconditioner Based on Automatic 3D Tetradedric Meshes

    Online Presentations | 04 Feb 2016 | Contributor(s):: Frederic Vi

    Multigrid methods are efficient for solving large sparse linear systems. Geometric (GMG) and Algebraic Multigrid (AMG) have both their own benefits and limitations. Combining the simplicity of AMG with the efficiency of GMG lead us to the development of an Hybrid Multigrid preconditionner. From...

  16. HPGMG: Benchmarking Computers Using Multigrid

    Online Presentations | 04 Feb 2016 | Contributor(s):: Jed Brown

    HPGMG (https://hpgmg.org) is a geometric multigrid benchmark designed to measure the performance and versatility of computers. For a benchmark to be representative of applications, good performance on the benchmark should be sufficient to ensure good performance on most important applications and...

  17. A Fast Multigrid Approach for Solving the Helmholtz Equation with a Point Source

    Online Presentations | 04 Feb 2016 | Contributor(s):: Eran Treister

    Solving the discretized Helmholtz equations with high wave numbers in large dimensions is a challenging task. However, in many scenarios, the solution of these equations is required for a point source. In this case, the problem can be be reformulated and split into two parts: one in a solution of...

  18. Compatible Relaxation Based Geometric-Algebraic Multigrid

    Online Presentations | 04 Feb 2016 | Contributor(s):: Fei Cao

    We develop compatible relaxation algorithms for smoothed aggregation-based multigrid coarsening. In the proposed method, we use the geometry of the given discrete problem on the finest level to coarsen the system together with compatible relaxation to from the sparsity structure of the...

  19. Space-time constrained FOSLS with AMGe upscaling

    Online Presentations | 04 Feb 2016 | Contributor(s):: Panayot Vassilevski

    We consider time-dependent PDEs discretized in combined space-time domains. We first reduce the PDE to a first order system. Very often in practice, one of the equations of the reduced system involves the divergence operator (in space-time). The popular FOSLS (first order system least-squares)...

  20. Stable Discretizations and Robust Block Preconditioners for Fluid-Structure Interaction Systems

    Online Presentations | 04 Feb 2016 | Contributor(s):: Kai Yang

    In our work we develop a family of preconditioners for the linear algebraic systems arising from the arbitrary Lagrangian-Eulerian discretization of some fluid-structure interaction models. After the time discretization, we formulate the fluid-structure interaction equations as saddle point...