next up previous contents index
Next: Conclusions Up: Some algorithms connected to Previous: A fast matrix vector   Contents   Index


The determinant of a semiseparable matrix in order $ O(n)$ flops.

In this section, we will design an order $ O(n)$ algorithm for calculating the determinant of a semiseparable matrix represented with the Givens-vector representation.

We will use the fact that the Givens transformations for representing the matrix in fact contain all the information needed for the $ QR$-factorization of the corresponding matrix. Using this information, we can very easily calculate the diagonal elements of the $ R$ factor of the semiseparable matrix. Multiplying these diagonal elements will give us the wanted determinant of the semiseparable matrix.

We have, because of the special structure of the representation, the Givens transformations $ G_1,\ldots,G_{n-1}$ such that applying $ G_{n-1}^T$ on the last two rows will annihilate all the elements except for the diagonal element, applying $ G_{n-2}^T$ on the third last and second last row, will annihilate all the elements in the second last row, except the last two elements (note that the Givens transformations by construction have the determinant equal to $ 1$). In this fashion we can continue very easily to annihilate all the elements in the strictly lower triangular part. In fact we are only interested in the diagonal elements. Performing these transformations will change the diagonal elements in the following way. Denote with $ d_i$ the diagonal elements of the semiseparable matrix, and with $ d^{(s)}_i$ the super diagonal elements. The diagonal elements $ i=2,\ldots,n$ change by performing:

% latex2html id marker 32114
$\displaystyle G^T_{i} \left( \begin{array}{c} d^{(...
...= \left( \begin{array}{c} \hat{d}^{(s)}_{i-1} \\  \hat{d}_i \end{array} \right)$    

where the elements $ \hat{d}_i$ denote the diagonal elements of the upper triangular matrix $ R$. Using this information one can easily deduce an order $ n$ algorithm for calculating the determinant.

More information about the $ QR$-factorization, from a computational point of view, can be found in Chapter 9 where the more general class of semiseparable plus diagonal matrices is considered. More information about the structure of the $ Q$ factor and the $ R$ factor, when calculating the $ QR$-factorization of a semiseparable plus diagonal matrix can be found in Chapter 1.


next up previous contents index
Next: Conclusions Up: Some algorithms connected to Previous: A fast matrix vector   Contents   Index
Raf Vandebril 2004-05-03