Bachelor's degree final project  v1.0
Faculty of Mathematics, University of Barcelona
Defines | Functions
LU factorization

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.

Detailed Description

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

The LU factorization of a rectangular matrix $ A \in \mathbb{R}(m, n) $ can also be performed and it is guaranteed to exists if $ A[1:i][1:i] $ is not singular for $ i = 1, \ldots, \min\{m, n\} $.
The calculation of a LU factorization of a rectangular matrix requires $ m n^2 - n^3 /3 $ flops and A can be overwritten by the strictly lower triangular portion of $ L \in \mathbb{R}(m, \min\{m, n\}) $ and the upper triangular portio of $ U \in \mathbb{R} (\min\{m, n\}, n)$.


Define Documentation

#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.

Partial pivoting by columns in LU decomposition.

Partial pivoting by rows in LU decomposition.

LU decomposition without any pivoting.


Function Documentation

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.

Parameters:
[in]mRows
[in]nColumns
[in]AMatrix n-by-n where will be computed LU factorization
[out]LUMatrix n-by-n where has been computed LU factorization
[out]prVector n-dimensional where will be saved the pivoting by rows
[out]pcVector n-dimensional where will be saved the pivoting by columns
[in]tolTolerance that indicates a diagonal's element is valid for applying the Gaussian elimination
Return values:
NULLIf tolerance is greater than the pivot in absolute value
1Otherwise
Precondition:
  • The dimension is greater than 1
  • The pointers A and LU are not NULL
  • The tolerance is positive
Postcondition:
  • The LU factorization has been saved in LU
  • The vector permutations (pr and pc) have been initialized, so the free should be done
Note:
  • LU and A can be the same
  • If pr is NULL and pc is NULL, pivoting will not be done
  • If pr is NULL and pc is not NULL, partial pivoting by columns will be done
  • If pr is not NULL and pc is NULL, partial pivoting by rows will be done
  • If pr is not NULL and pc is not NULL, full pivoting will be done

References FULL_PIVOTING, lu_flag(), PARTIAL_PIVOTING_COL, PARTIAL_PIVOTING_ROW, and WHITOUT_PIVOTING.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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.

Parameters:
[in]mRows
[in]nColumns
[in]AMatrix m-by-n where will be computed LU factorization
[out]LUMatrix m-by-n where has been computed LU factorization
[out]prVector m-dimensional where will be saved the pivoting by rows
[out]pcVector n-dimensional where will be saved the pivoting by columns
[in]tolTolerance that indicates a diagonal's element is valid for applying the Gaussian elimination
[in]flagType of pivoting
Return values:
NULLIf tolerance is greater than the pivot in absolute value
1Otherwise
Precondition:
  • The dimension are greater than 1
  • The pointers A and LU are not NULL
  • The tolerance is positive
  • Row vector permutation pointer and Column vector permutation are either NULL or else different
Postcondition:
  • The LU factorization has been saved in LU
  • The vector permutations (pr and pc) can have been initialized, so the free should be done
Note:

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.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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.

Parameters:
[in]nDimension of matrixs
[in]AMatrix m-by-n where will be read the column
[in]idxRow index
[out]colColumn index with the first maximum value
Returns:
The first maximum value in absolute value in the row index
Precondition:
The indexs is less than the dimension and the pointer is not NULL
Note:
The column indexes can be the same

+ Here is the caller graph for this function:

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.

Parameters:
[in]mDimension of matrixs
[in]AMatrix m-by-n where will be read the column
[in]idxColumn index
[out]rowRow index with the first maximum value
Returns:
The first maximum value in absolute value in the column index
Precondition:
Dimension is not 0, the indexs is less than the dimension and the pointer is not NULL
Note:
The row indexes can be the same

+ Here is the caller graph for this function:

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.

Parameters:
[in]mRows
[in]nColumns
[in]AMatrix m-by-n where will be read the column
[in]idxIndex
[out]rowRow index
[out]colColumn index
Returns:
The maximum value in absolute value
Precondition:
  • The indexs is less than the dimension
  • The pointers are not NULL
Postcondition:
Either row index or else column index is different than idx index
Note:
The column indexes can be the same

+ Here is the caller graph for this function:

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.

Parameters:
[in]iIndex
[in]jIndex
[in]xSource vector
[out]yDestination vector
Note:
The vectors can be the same. If one of them is NULL, anything is done

+ Here is the caller graph for this function:

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.

Parameters:
[in]col1Col index
[in]col2Col index
[in]mRows
[in]AMatrix m-by-n where will be read the rows
[out]BMatrix m-by-n where will be saved the rows
Precondition:
  • The indexs are less than the number of rows
  • The pointers are not NULL
Postcondition:
The swapping is in B
Note:
  • The column indexes can be the same
  • The matrix can be the same

+ Here is the caller graph for this function:

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.

Parameters:
[in]row1Row index
[in]row2Row index
[in]nColumns
[in]AMatrix m-by-n where will be read the rows
[out]BMatrix m-by-n where will be saved the rows
Precondition:
  • The indexs are less than the number of rows
  • The pointers are not NULL
Postcondition:
The swapping is in B
Note:
  • The row indexes can be the same
  • The matrix can be the same

+ Here is the caller graph for this function: