Bachelor's degree final project  v1.0
Faculty of Mathematics, University of Barcelona
Functions
Solving a linear of equations system

Solving the system is find a vector x satisfying the linear equation Ax = b. More...

Functions

void forward_substitution_ones (size_t n, double **const L, double *const x, double *const b)
 Forward substitution for lower triangular matrices (Lx = b) where the diagonal of L are 1's.
void * forward_substitution (size_t n, double **const L, double *const x, double *const b, double tol)
 Forward substitution for lower triangular matrices (Lx = b)
void * back_substitution (size_t n, double **const U, double *const x, double *const b, double tol)
 Back substitution for upper triangular matrices (Ux = b)
void * solve_qr (size_t m, size_t n, double **const A, double *const x, double *const b, double tol)
 QR solve linear system (QRx = b)
void * solve_lu (size_t m, size_t n, double **const A, double *const x, double *const b, double tol)
 LU solve linear system (LUx = b)
void * solve (size_t m, size_t n, double **const A, double *const x, double *const b, double tol, void *(*s)(size_t, size_t, double **const, double *const, double *const, double))
 solve a linear system (Ax = b) with the pointer to a solve function
solve_ptr get_solve_with_lu ()
solve_ptr get_solve_with_qr ()

Detailed Description

Solving the system is find a vector x satisfying the linear equation Ax = b.

The standard algorithm for solving a system of linear equations is based on Gaussian elimination with some modifications. Firstly, it is essential to avoid division by small numbers, which may lead to inaccurate results. This can be done by reordering the equations if necessary, a process known as pivoting. Secondly, the algorithm does not exactly do Gaussian elimination, but it computes the LU factorization of the matrix A. Other useful algorithm for solving a linear system is to compute QR factorization of the matrix A. This leads to the class of direct methods.
If the matrix A has some special structure, this can be exploited to obtain faster or more accurate algorithms. For instance, systems with a symmetric matrix or a symmetric positive definite matrix or a strictly diagonaly dominant matrix, ... Special methods exist also for matrices with many zero elements (so-called sparse matrices).
A completely different approach is often taken for very large systems, which would otherwise take too much time or memory. The idea is to start with an initial approximation to the solution (which does not have to be accurate at all), and to change this approximation in several steps to bring it closer to the true solution. Once the approximation is sufficiently accurate, this is taken to be the solution to the system. For instance, Jacobi method, Gauss-Seidel method, Successive over-relaxation (SOR) method, ... This leads to the class of iterative methods.
In this module, we implement some of these methods


Function Documentation

void* back_substitution ( size_t  n,
double **const  U,
double *const  x,
double *const  b,
double  tol 
)

Back substitution for upper triangular matrices (Ux = b)

Parameters:
[in]nDimension of matrix and vectors
[in]UUpper triangular matrix
[in]bConstant terms
[out]xUnknowns
[in]tolTolerance
Return values:
NULLIf some diagonal's element is less than or equal to tolerance
1Otherwise
Precondition:
  • The pointers are not NULL
  • The tolerance is positive
Postcondition:
The vector x has the solution
Note:
The complexity is $ O(n^2) $

+ Here is the caller graph for this function:

void* forward_substitution ( size_t  n,
double **const  L,
double *const  x,
double *const  b,
double  tol 
)

Forward substitution for lower triangular matrices (Lx = b)

Parameters:
[in]nDimension of matrix and vectors
[in]LLower triangular matrix
[in]bConstant terms
[out]xUnknowns
[in]tolTolerance
Return values:
NULLIf some diagonal's element is less than or equal to tolerance
1Otherwise
Precondition:
  • The pointers are not NULL
  • The tolerance is positive
Postcondition:
The vector x has the solution
Remarks:
The complexity is $ O(n^2) $
void forward_substitution_ones ( size_t  n,
double **const  L,
double *const  x,
double *const  b 
)

Forward substitution for lower triangular matrices (Lx = b) where the diagonal of L are 1's.

Parameters:
[in]nDimension of matrix and vectors
[in]LLower triangular matrix with 1's in its diagonal
[in]bConstant terms
[out]xUnknowns
Precondition:
The pointers are not NULL
Postcondition:
The vector x has the solution
Remarks:
The complexity is $ O(n^2) $

+ Here is the caller graph for this function:

References SOLVE_WITH_LU.

References SOLVE_WITH_QR.

void * solve ( size_t  m,
size_t  n,
double **const  A,
double *const  x,
double *const  b,
double  tol,
void *(*)(size_t, size_t, double **const, double *const, double *const, double)  s 
)

solve a linear system (Ax = b) with the pointer to a solve function

Parameters:
[in]nDimension of matrix and vectors
[in,out]AMatrix's system
[in]bConstant terms
[out]xUnknowns
[in]tolTolerance
[in]sPointer to a function that solve the linear system
Returns:
The value that is returned by the pointer to the solve function
Precondition:
The dimension is greater than one
Postcondition:
The x vector has the solution
See also:
SOLVE_WITH_LU and SOLVE_WITH_QR

References solve_lu(), solve_qr(), SOLVE_WITH_LU, and SOLVE_WITH_QR.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void* solve_lu ( size_t  m,
size_t  n,
double **const  A,
double *const  x,
double *const  b,
double  tol 
)

LU solve linear system (LUx = b)

Parameters:
[in]nDimension of matrix and vectors
[in,out]AMatrix's system
[in]bConstant terms
[out]xUnknowns
[in]tolTolerance
Return values:
NULLWhen LU factorization was unsuccessful or could not be allocated memory
1Otherwise
Precondition:
The dimension is greater than one
Postcondition:
The x vector has the solution
Note:
  • The vector of constant terms will be modified
  • The unknowns pointer x and constant terms pointer b can be the same
See also:
lu

References back_substitution(), forward_substitution_ones(), FULL_PIVOTING, lu(), PARTIAL_PIVOTING_COL, PARTIAL_PIVOTING_ROW, permutation_vector(), and WHITOUT_PIVOTING.

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void* solve_qr ( size_t  m,
size_t  n,
double **const  A,
double *const  x,
double *const  b,
double  tol 
)

QR solve linear system (QRx = b)

Parameters:
[in]nDimension of matrix and vectors
[in,out]AMatrix's system
[in,out]bConstant terms
[out]xUnknowns
Return values:
NULLWhen QR factorization was unsuccessful or could not be allocated memory
1Otherwise
Precondition:
The dimension is greater than one
Postcondition:
The x vector has the solution
Note:
  • The vector of constant terms will be modified
  • The unknowns pointer x and constant terms pointer b can be the same
See also:
qr

References back_substitution(), premult_Q_vector(), and qr().

+ Here is the call graph for this function:

+ Here is the caller graph for this function: