![]() |
Bachelor's degree final project
v1.0
Faculty of Mathematics, University of Barcelona
|
Implement the LU decomposition of a square matrix with partial pivoting (rows or columns) or full pivoting are admitted. More...
Defines | |
#define | WHITOUT_PIVOTING |
LU decomposition without any pivoting. | |
#define | PARTIAL_PIVOTING_ROW |
Partial pivoting by rows in LU decomposition. | |
#define | PARTIAL_PIVOTING_COL |
Partial pivoting by columns in LU decomposition. | |
#define | FULL_PIVOTING |
Complete pivoting by rows and columns in LU decomposition. | |
#define | _OPENMP_LU_DIMENSION 1e2 |
Minimum value for using the openmp library in LU decomposition. | |
Functions | |
double | max_row (size_t m, double **const A, size_t idx, size_t *const row) |
Find the maximum value of a column based on the same row index. | |
double | max_col (size_t n, double **const A, size_t idx, size_t *const col) |
Find the first maximum value of a column based on the same column index. | |
double | max_row_col (size_t m, size_t n, double **const A, size_t idx, size_t *const row, size_t *const col) |
Find the maximum value of a column and row based on the same column and row index. | |
void | swap_bit (size_t i, size_t j, size_t *const x, size_t *const y) |
Swap two values from vector x to y. | |
void | swap_row (size_t row1, size_t row2, size_t n, double **const A, double **const B) |
Swap two rows from matrix A to B based on the same minimum row index. | |
void | swap_col (size_t col1, size_t col2, size_t m, double **const A, double **const B) |
Swap two columns from matrix A to B based on the same minimum column index. | |
void * | lu_flag (size_t m, size_t n, double **const A, double **const LU, size_t *const pr, size_t *const pc, double tol, unsigned int flag) |
Compute the LU factorization of a matrix m-by-n with a specific pivoting. | |
void * | lu (size_t m, size_t n, double **const A, double **const LU, size_t *const pr, size_t *const pc, double tol) |
Compute the LU factorization of a matrix n-by-n. |
Implement the LU decomposition of a square matrix with partial pivoting (rows or columns) or full pivoting are admitted.
Let A be a square matrix. An LU factorization refers to the factorization of A, with proper row and/or column orderings or permutations, into two factors, a lower triangular matrix L with 1 in its diagonal and an upper triangular matrix U, that is A = LU.
It turns out that a proper permutation in rows (or columns) is sufficient for the LU factorization. The LU factorization with Partial Pivoting by rows refers often to the LU factorization with row permutations only, that can be denoted by PA = LU, where P is a permutation matrix which, when left-multiplied to A, reorders the rows of A.
The LU factorization with Partial Pivoting by columns refers to the LU factorization with column permutations, that can be denoted by AQ = LU where Q is a permutation matrix that reorders the columns of A.
It turns out that all square matrices can be factorized in this form, and the factorization is numerically stable in practice.
An LU factorization with full pivoting involves both row and column permutations, that can be denoted by PAQ = LU.
The LU factorization of a rectangular matrix can also be performed and it is guaranteed to exists if
is not singular for
.
The calculation of a LU factorization of a rectangular matrix requires flops and A can be overwritten by the strictly lower triangular portion of
and the upper triangular portio of
.
#define _OPENMP_LU_DIMENSION 1e2 |
Minimum value for using the openmp library in LU decomposition.
#define FULL_PIVOTING |
Complete pivoting by rows and columns in LU decomposition.
#define PARTIAL_PIVOTING_COL |
Partial pivoting by columns in LU decomposition.
#define PARTIAL_PIVOTING_ROW |
Partial pivoting by rows in LU decomposition.
#define WHITOUT_PIVOTING |
LU decomposition without any pivoting.
void* lu | ( | size_t | m, |
size_t | n, | ||
double **const | A, | ||
double **const | LU, | ||
size_t *const | pr, | ||
size_t *const | pc, | ||
double | tol | ||
) |
Compute the LU factorization of a matrix n-by-n.
[in] | m | Rows |
[in] | n | Columns |
[in] | A | Matrix n-by-n where will be computed LU factorization |
[out] | LU | Matrix n-by-n where has been computed LU factorization |
[out] | pr | Vector n-dimensional where will be saved the pivoting by rows |
[out] | pc | Vector n-dimensional where will be saved the pivoting by columns |
[in] | tol | Tolerance that indicates a diagonal's element is valid for applying the Gaussian elimination |
NULL | If tolerance is greater than the pivot in absolute value |
1 | Otherwise |
References FULL_PIVOTING, lu_flag(), PARTIAL_PIVOTING_COL, PARTIAL_PIVOTING_ROW, and WHITOUT_PIVOTING.
void * lu_flag | ( | size_t | m, |
size_t | n, | ||
double **const | A, | ||
double **const | LU, | ||
size_t *const | pr, | ||
size_t *const | pc, | ||
double | tol, | ||
unsigned int | flag | ||
) |
Compute the LU factorization of a matrix m-by-n with a specific pivoting.
[in] | m | Rows |
[in] | n | Columns |
[in] | A | Matrix m-by-n where will be computed LU factorization |
[out] | LU | Matrix m-by-n where has been computed LU factorization |
[out] | pr | Vector m-dimensional where will be saved the pivoting by rows |
[out] | pc | Vector n-dimensional where will be saved the pivoting by columns |
[in] | tol | Tolerance that indicates a diagonal's element is valid for applying the Gaussian elimination |
[in] | flag | Type of pivoting |
NULL | If tolerance is greater than the pivot in absolute value |
1 | Otherwise |
References copy_matrix(), FULL_PIVOTING, max_col(), max_row(), max_row_col(), PARTIAL_PIVOTING_COL, PARTIAL_PIVOTING_ROW, permutation_init(), swap_bit(), swap_col(), swap_row(), and WHITOUT_PIVOTING.
double max_col | ( | size_t | n, |
double **const | A, | ||
size_t | idx, | ||
size_t *const | col | ||
) |
Find the first maximum value of a column based on the same column index.
[in] | n | Dimension of matrixs |
[in] | A | Matrix m-by-n where will be read the column |
[in] | idx | Row index |
[out] | col | Column index with the first maximum value |
double max_row | ( | size_t | m, |
double **const | A, | ||
size_t | idx, | ||
size_t *const | row | ||
) |
Find the maximum value of a column based on the same row index.
[in] | m | Dimension of matrixs |
[in] | A | Matrix m-by-n where will be read the column |
[in] | idx | Column index |
[out] | row | Row index with the first maximum value |
double max_row_col | ( | size_t | m, |
size_t | n, | ||
double **const | A, | ||
size_t | idx, | ||
size_t *const | row, | ||
size_t *const | col | ||
) |
Find the maximum value of a column and row based on the same column and row index.
[in] | m | Rows |
[in] | n | Columns |
[in] | A | Matrix m-by-n where will be read the column |
[in] | idx | Index |
[out] | row | Row index |
[out] | col | Column index |
void swap_bit | ( | size_t | i, |
size_t | j, | ||
size_t *const | x, | ||
size_t *const | y | ||
) |
Swap two values from vector x to y.
[in] | i | Index |
[in] | j | Index |
[in] | x | Source vector |
[out] | y | Destination vector |
void swap_col | ( | size_t | col1, |
size_t | col2, | ||
size_t | m, | ||
double **const | A, | ||
double **const | B | ||
) |
Swap two columns from matrix A to B based on the same minimum column index.
[in] | col1 | Col index |
[in] | col2 | Col index |
[in] | m | Rows |
[in] | A | Matrix m-by-n where will be read the rows |
[out] | B | Matrix m-by-n where will be saved the rows |
void swap_row | ( | size_t | row1, |
size_t | row2, | ||
size_t | n, | ||
double **const | A, | ||
double **const | B | ||
) |
Swap two rows from matrix A to B based on the same minimum row index.
[in] | row1 | Row index |
[in] | row2 | Row index |
[in] | n | Columns |
[in] | A | Matrix m-by-n where will be read the rows |
[out] | B | Matrix m-by-n where will be saved the rows |