Stable Gauss Factorization

To obtain a stable and efficient Gauss factorization also valid for underdimensioned systems, certain modifications are called for with respect to traditional factorization. 

The third device is to invert the optimal pivoting criterion. Traditionally, the optimal pivot is selected for each column. This ensures the best equation is selected for each variable. 

In the case of underdimensioned systems, it is preferable to select the optimal pivot for each row. This ensures the best variable is selected for each equation. 

The BzzFactorizedGaussAttic class in the BzzMath library solves square or underdimensioned linear systems with dense matrices using a stable Gauss factorization. 

The BzzFactorizedGaussAttic name comes from the fact that the first time it was used to solve a linear programming problem with the Attic method (see Chapter 10). The BzzFactorizedGaussAttic class includes the default constructor only. An object from this class is initialized using as the argument the matrix of the system and its right-hand side terms. 

---

Replace orthogonal projection by evaluating the nuD space N with the procedure described in the next section that exploits stable Gauss factorization of a system in which the variables are separated into m dependent variables, xj, and n m independent variables, x . This is the optimal choice for large-scale sparse systems when the equations are preventively normalized and the dependent variables are carefully selected. 

When E is large and sparse, LQ factorization can be computationally onerous and lead to the dangerous matrix filling as well in this case a stable Gauss factorization is required to calculate the null space of the matrix (see Chapter 8). 

The difference between the vector projection and the use of null space of the constraints to obtain a vector that satisfies them was discussed in Chapter 8 and in Section 11.3.3. We have also seen that LQ factorization can be adopted to get the projection for small dimension problems, whereas it is preferable to use the null space obtained with stable Gauss factorization for large-scale systems. 

Lastly, it is also possible to use the method that exploits the null space of the constraints. Once again in this case, all the active bounds must first be removed from the problem. Only then it is possible to use either LQ factorization or a stable Gauss factorization of all the equality and active inequality constraints. This gives the KKT conditions for an unconstrained problem, as has already been demonstrated for equality constraints. 

Chapter 8 deals with underdimensioned nonlinear systems. It proposes a stable Gauss factorization for their solution and compares the novel method to the most common factorizations. Sparse underdimensioned nonlinear systems also have a dedicated class of algorithms. 

Recently (Buzzi-Ferraris, 2011a) proposed a novel Gauss factorization that allows the factorization of an underdimensioned matrix in a stable way (see Section 8.2). 

The second defect of LQ factorization is important for sparse matrices. In fact, dense matrices require double the computational effort of Gauss factorization. If the matrix is sparse, this gap may become larger and a dramatic filling of the factorized matrix may occur. The advantages of LQ factorization are a stable solution of an underdimensioned system (if the system is standardized), and the easy and safe removal of all linear combinations among equations. 

To use this technique, the Gauss factorization must be stable this factor must always be kept in mind in the selection of the variables to be used as dependent variables. 

---