Difference between revisions of "LU Decomposition"
| Line 31: | Line 31: | ||
[[File:pseudocode.png|center]] | [[File:pseudocode.png|center]] | ||
| + | |||
| + | [[File:ludgif.gif|center|500px]] | ||
= nu+ Optimization = | = nu+ Optimization = | ||
| + | |||
| + | In this section, it is shown how the pseudo-code algorithm can be optimized using nu+ features. | ||
| + | |||
| + | == Pivoting phase == | ||
| + | |||
| + | The pivoting phase has been made multi-threaded. | ||
| + | Every k-th iteration (k ranging from 0 to m-1) of the pivoting operations works on the elements belonging to the k-th column and to rows from k to m-1. | ||
Revision as of 18:20, 2 February 2018
Contents
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
nu+ Optimization
In this section, it is shown how the pseudo-code algorithm can be optimized using nu+ features.
Pivoting phase
The pivoting phase has been made multi-threaded. Every k-th iteration (k ranging from 0 to m-1) of the pivoting operations works on the elements belonging to the k-th column and to rows from k to m-1.
