Difference between revisions of "LU Decomposition"
From NaplesPU Documentation
| Line 16: | Line 16: | ||
* [[File:U.png|15px]] upper triangolar matrix | * [[File:U.png|15px]] upper triangolar matrix | ||
* [[File:L.png|15px]] lower triangolar matrix | * [[File:L.png|15px]] lower triangolar matrix | ||
| + | |||
| + | ==Partial Pivoting == | ||
| + | Partial pivoting is an optimization of standard LU Decomposition that aims to reduce numerical instability | ||
| + | |||
| + | * Therefore a matrix [[File:P.png|15px]] is needed to keep track of pivoting operations | ||
| + | * Partial because pivoting is applied on rows only | ||
| + | |||
| + | These matrices have to verify the relation: | ||
| + | |||
| + | |||
| + | [[File:PA=LU.png|center|75px]] | ||
| + | |||
| + | ==Pseudocode== | ||
| + | |||
| + | [[File:pseudocode.png|center]] | ||
Revision as of 22:52, 1 February 2018
Summary
LU Decomposition is an example of how to use Nu+ features to optimize an algorithm, using multithreaded and vectorial code.
Reusable code decomposition and multithreaded and vectorial optimization methods are shown; they can be applied to every other parallelizable algorithm, from image processing to machine learning ones.
Algorithm Description
LU Decomposition is used in solving systems of linear equations
Algorithm decomposes A in:
-
upper triangolar matrix -
lower triangolar matrix
Partial Pivoting
Partial pivoting is an optimization of standard LU Decomposition that aims to reduce numerical instability
- Therefore a matrix
is needed to keep track of pivoting operations - Partial because pivoting is applied on rows only
These matrices have to verify the relation:
Pseudocode
