Permuations in Structured Numerical Problems

Ketil Malde
Institutt for informatikk, 1996

• Contents
  • Introduction
    • Object Orientation
    • Permutations
    • Problems and Algorithms
    • Library
    • Further Theory and Analysis
• Basic Permutations
  • Background
    • The Structure of Algorithms
    • The Parallel View
    • The Object Oriented View
  • Permutations in Algorithms
    • Rings
    • Basic Data Structures
    • Parameters
    • Permutations
    • Matrix Permutations
    • Shifts
    • Hierarchical Reshapes
    • Reduction and Prolongation
    • Stencils
    • Operations on Permutations
• Numerical Algorithms
  • Matrix multiplication
    • Algorithm
    • Test Problems
    • Implementation
    • Conclusion
  • Fast Fourier Transform
    • Algorithm
    • Test Case Problems
    • Implementation Considerations
    • Conclusion
  • Multigrid Linear Solvers
    • The Jacobi Algorithm
    • The Multigrid Algorithm
    • Test Case Problems
    • Implementation
    • Conclusion
  • Cyclic Reduction
    • Background
    • Algorithm
    • Implementation
    • Conclusion
  • The Fast Wavelet Transform
    • Background
    • Algorithm
    • Implementation
    • Conclusions
  • Conclusions
    • Feasibility
    • Complexity and Costs
• Implementation
  • General
    • Notes on Coding Style
    • IO and Storage
    • Run time error checking
    • Compilation and External Dependencies
  • Overview
    • Intended Usage
    • Inheritance
    • Parameterized Classes
    • Compatibility
  • The Array Class
    • Basic Idea
    • Enhancements
    • Class Dependencies and Provisions
    • Implementation Issues
  • The Shape class
    • Basic Idea
    • Class Dependencies and Provisions
    • Implementation issues
    • The Complexity of Member Functions
    • The ShapedObject ABC
    • ShapedObject Member Functions
    • The Index class
  • The Grid class
    • Basic Idea
    • Class Dependencies
    • Implementation Issues
    • Complexity of Member Functions
  • Permutation Operator Classes
    • The PermOp ABC
    • PMatrix - linear permutations
    • SVector - linear shifts
    • Affine - affine transformations
    • Stencil - convolutions
    • Hierarchical Reshapes
    • Reduction and Prolongation
  • Further Sequential Optimizations
    • The Array Class
    • The ShapedObject Class Family
    • The Grid Class
    • The PermOp Class Family
  • Parallel Implementation Hints
    • Arrays and Shapes
    • Distributing Grids
  • Conclusions
  • General DFT and FFT
    • A Note On Terminology
    • Reiterating DFT
    • Shift Operators
    • The multidimensional case
    • DFT on Abelian Groups
    • The FFT on an Abelian Group
    • The FFT Algorithm
  • Convergence of Iterative Solvers
  • Some Parallel Architectures
    • Single Instruction, Multiple Data
    • Multiple Instruction Multiple Data
    • Symmetric Multiprocessing
    • Distributed Systems/Clusters
• References
• About this document ...