Gauss factorization

The Jacobian is factorized in the solution of the system (7.38). The original solvers used Gauss factorization (or its PLR variant) since it is the least computationally onerous later on, however, many authors recommended QR factorization because... 

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

If QR or LQ factorization is adopted, it is possible to use the methods described by Buzzi-Ferraris and Manenti (2010a), which are also less efficient than the ones used to update a symmetric matrix. On the other hand, if a Gauss factorization is adopted the problem is more complex and some stability problems may arise with the algorithm. 

Number of Newton method applications 13 Number of Quasi Newton method applications 73 Number of analytical Jacobian evaluations 0 Number of numerical Jacobian evaluations 13 Number of Gradient searches 0 Number of Gauss factorizations 7 Number of LQ factorizations 13 Number of linear system solutions 172... 

The m equations (8.3) with the n — m conditions (8.12) make the system square and, consequently, solvable through an appropriate algorithm (i.e.. Gauss factorization) when the resulting matrix is nonsingular. As special but important case, the values cj are all zero. Also to obtain a solution of the underdimensioned linear system that can exploit the Gauss factorization, the variables x are separated into m dependent variables, x, and into n — m independent variables, x , to which a numerical value is assigned. 

The matrix condition number (traditional approach without weighing the right-hand side terms) is 242 hence, the system should be considered well conditioned. The system conditioning is small too and is 5.4. If we solve this system with a traditional Gauss factorization without passing through the standard form, the selected pivot for the first column is 10 since it is... 

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. 

If a Gauss factorization is used to solve the system and the pivot is selected as the best on the column after having balanced all the coefficients of such a column, the following solution would be... 

The majority of the programs that exploit Gauss factorization select the pivot without any column swap, but with row swaps only, when needed. It is effective only if the matrix is square and relatively well conditioned. 

In the previous example, if the pivoting is performed in a cleverer way, using another a more sophisticated Gauss factorization that performs a column swap in... 

Clearly, it is possible to achieve a reasonable solution of an underdimensioned system using the Gauss factorization, only if the independent variable selection is performed adequately. 

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. 

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

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

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. 

In the BzzMath library, the BzzQuadraticPrograrmning class uses LQ factorization for small-medium dense problems and Gauss factorization for medium-large sparse problems. 

In Chapter 8, we showed that in the case of linear constraints with the matrix A m < n it is possible to obtain the null space of the matrix using a Gauss factorization with good stability features. 

The main difference with projection methods is in the use of the null space of the active constraints obtained with Gauss factorization in spite of the projection matrix. 

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. 

In the BzzConstrainedMinimization class the Gauss factorization is used in large sparse problems. 

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. 

---