Householder algorithm

When any such preselection of configurations has been performed, one is often faced with the problem that 10-300,000 configurations have to be included in the final Cl calculation. Conventional matrix diagonalization routines such as the one used in the Householder algorithm, which modifies the elements of the matrix as it proceeds, cannot be used to determine the eigenvalues and eigenvectors of the Cl matrix. For this reason, specialized approaches have been developed (Schaefer and Miller, 1977, Chapters 7 and... 

Of all of the methods, including the modified Gram-Schmidt and Householder algorithm (Buzzi-Ferraris and Manenti, 2010a), the technique proposed by Powell (1968) is the preferred one. 

A comparison of the performance of the three algorithms for eigenvalue decomposition has been made on a PC (IBM AT) equipped with a mathematical coprocessor [38]. The results which are displayed in Fig. 31.14 show that the Householder-QR algorithm outperforms Jacobi s by a factor of about 4 and is superior to the power method by a factor of about 20. The time for diagonalization of a square symmetric value required by Householder-QR increases with the power 2.6 of the dimension of the matrix. 

Instead of applying Householder s formula, the calculation of an inverse of the jacobian may be avoided altogether by use of the algorithm proposed by Bennett for updating the LU factors of the jacobian matrix. Example 4-9 will show that fewer numerical operations are required to compute the LU factors than are required to compute the inverse of a matrix. Bennett s algorithm is applied to the Broyden equations as follows. 

Less time is consumed by procedure 3 than by procedure 1. Calculation of the LU factors of the matrix J in step 2 of procedure 3 requires approximately n3/3 operations, whereas the calculation of the inverse of J in step 2 of procedure 2 requires approximately n3 operations, where the matrix J is a square matrix of order n. To update the LU factors in step 6 of procedure 3 by use of Bennett s algorithm requires approximately In2 operation, whereas approximately 3n2 operations are required to update the inverse of J by use of Householder s formula as proposed by Broyden in step 6 of procedure 2. 

After the Broyden correction for the independent variables has been computed, Broyden proposed that the inverse of the jacobian matrix of the Newton-Raphson equations be updated by use of Householder s formula. Herein lies the difficulty with Broyden s method. For Newton-Raphson formulations such as the Almost Band Algorithm for problems involving highly nonideal solutions, the corresponding jacobian matrices are exceedingly sparse, and the inverse of a sparse matrix is not necessarily sparse. The sparse characteristic of these jacobian matrices makes the application of Broyden s method (wherein the inverse of the jacobian matrix is updated by use of Householder s formula) impractical. 

In this algorithm, Broyden s method is applied by updating the jacobian matrices by use of Householder s formula.13 Let J0 be the initial approximation of the jacobian matrix with which the iterative procedure is started. Then... 

An algorithm is given elow for solving the Newton-Raphson equations by use of only the LU factorization of J0 and the Broyden update terms given by Eqs. (5-29), (5-30), and (5-31). As shown in App. 5-1, this algorithm is based on the successive application of Householder s formula to Eq. (5-29). 

Like the Broyden-Householder method, Kubicek algorithm is based on Householder s identity.19... 

Typical procedures to solve the OLS problem are Gaussian elimination and Gauss-Jordan elimination. More efficient solutions are based on decomposition of the X matrix by algorithms, such as LU decomposition. Householder reduction, or singular value decomposition (SVD). One of the most powerful methods, SVD, is outlined as follows (cf. Section 5.2 and Biased Parameter Estimations PCR and PLS Section). 

Householder transformation with column pivoting can be applied to a matrix A in order to compute the least-squares solution to Ac = f even where A does not have full rank, that is, where r = rank(A) < n[Pg.190]

A little more expensive [n (m + I7nl3) flops and 2mn space versus n (m—nl3) and mn in the Householder transformation] but completely stable algorithm relies on computing the singular value decomposition (SVD) of A. Unlike Householder s transformation, that algorithm always computes the least-squares solution of the minimum 2-norm. The SVD of an m x n matrix A is the factorization A = ITEV, where U and V are two square orthogonal matrices (of sizes mxm and nxn, respectively), U U = Im, y V = In, and where the m x n matrix S... 

We describe here an algorithm based on Householder transformations (reflections). For any w e with m> I = 1, we can generate the matrix... 

---