Transcript Dileep Mardhamx

Parallel Direct Methods for Sparse Linear
Systems
Contents
•
•
•
•
•
Problem Statement
Motivation
Types of Algorithms
Sparse Matrices
Methods to solve Sparse Matrices
Problem Statement
Problem Statement
• The solution of the linear system is the values of the
unknown vector x, that satisfy every equation in the linear
system for the given matrix A and vector b
Why Linear Systems?
• How many liters of a 70% alcohol solution must be added to 50 liters of a
40% alcohol solution to produce a 50% alcohol solution?
– Manufacturing companies use a system of linear equations to solve these kind of
problems in their production line.
– Oil and Gas companies makes adjustments to their recipes for manufacturing gas and
diesel based on the component prices.
– Even hotdog companies do that and so on…
All these problems can be solved using linear system solvers.
Algorithms
• There has been several algorithms proposed to solve
linear systems. They can be categorized as
– Direct Methods
• Gaussian Algorithm – O(n3)
• Cholesky Factorization etc.,
– Iterative Methods
• Jacobi Method
• The Conjugate Gradient Method
The Gauss method
• The main idea of the method is by using the equivalent operations to
transform a dense system into an upper triangular system, which can be
easily solved
• Equivalent transformations:
–Multiplying an equation by a nonzero constant,
–Interchanging two equations,
–Adding an equation multiplied by a constant to another equation
The Gauss method
• On the first stage of the algorithm, which is called the Gaussian elimination,
the initial system of linear equations is transformed into an upper triangular
system by the sequential elimination of unknowns:
Ux = c
• On the second stage of the algorithm, which is called the back substitution,
the values of the variables are calculated
Example
• Complexity is O(n3)
• Some real time applications have massive sizes for A.
• It will take years to solve such linear systems using
Gaussian Method.
• This method is not well-suited for sparse systems.
– Increases storage and total Flops count.
Sparse System
• A system of linear equations is called sparse if only a relatively small number
of its matrix elements aij are nonzero.
• It is wasteful to use general methods of linear algebra on such problems,
because most of the O(N3) arithmetic operations devoted to solving the set of
equations or inverting the matrix involve zero operands.
Sparse matrices arise in ...
• computational fluid dynamics, finite-element methods, statistics,
time/frequency domain circuit simulation, dynamic and static modeling of
chemical processes, cryptography, magneto-hydrodynamics, electrical
power systems, differential equations, quantum mechanics, structural
mechanics (buildings, ships, aircraft, human body parts...), heat transfer,
MRI reconstructions, vibroacoustics, linear and non-linear optimization,
financial portfolios, semiconductor process simulation, economic
modeling, oil reservoir modeling, astrophysics, crack propagation,
Google page rank, 3D computer vision, cell phone tower placement,
tomography, multibody simulation, model reduction, nano-technology,
acoustic radiation, density functional theory, quadratic assignment, elastic
properties of crystals, natural language processing, DNA electrophoresis,
...
Example in structural mechanics:
Sparse data structures
• compressed sparse column format
Factorization process
• Solution of Ax = b
– A is unsymmetric :
• A is factorized as: A = LU, where
– L is a lower triangular matrix, and
– U is an upper triangular matrix.
• Forward-backward substitution: Ly = b then Ux = y
– A is symmetric:
• positive definite A = LLT
Cholesky Factorization Algorithm
• Cholesky Factorization is a variant of Gaussian
elimination that takes advantage of symmetry to reduce
both work and storage by about half.
Next Presentation….
• Discuss about “SuiteSparse”, an API which has
implementations of various algorithms for solving
Sparse Systems.
• How GPU acceleration can be achieved for
Cholesky Factorization?
• Complexity analysis of Sequential and Parallel
versions of the algorithm.
QUESTIONS ?