0

Let a matrix $A\in \mathbb{R}^{n\times n}$ be of the form

\begin{pmatrix} \alpha_1 & \gamma_1 & \gamma_2 &... &\gamma_{n-1} \\ \beta_2 & \alpha_2 & 0 & ... & 0\\ \beta_3 & 0 & \alpha_3 & ...&0 \\ \vdots & 0 & \ddots& ...&0\\ \beta_n& & &&\alpha_n \end{pmatrix}

Design an algorithm to obtain the QR decomposition of A using Givens transformation in $O(n^2)$ operations .

We know that Given transformation in Hessenberg matrix take $O(n^2) $ time complexity . Hene i first try to convert this matrix into Hessenberg matrix then want to use Givens algorithm .But converting Hessenberg matris using Housholder takes $O(n^3)$ complexity, so that is not perform here . Hence how to perform this process ??

Aritra Roy
  • 109

1 Answers1

0

Because of the layout of $A$, you need to apply $n - 1$ Givens rotations from the left to bring it to upper triangular form, since you only have $n - 1$ elements to eliminate (the first column of $A$).

For example, let $$ G_1 = \begin{bmatrix} I_{n-2} & \boldsymbol{0} & \boldsymbol{0} \\ \boldsymbol{0} &c & -s \\ \boldsymbol{0} & s& c \end{bmatrix} $$

Applying $G_1$ to $A$ from the left will make the last $2$ rows of $A$ look like $$ \begin{bmatrix} c \beta_{n-1} -s \beta_n & 0 & \dots & c \alpha_{n-1} & 0 \\ s \beta_{n-1} +c \beta_n & 0 & \dots & 0 & s \alpha_n \end{bmatrix} $$

On the other hand, applying a single Givens rotation takes time $O(n)$, because you are editing at most $2$ rows of $A$ of at most $n$ elements each. Do you see how to continue from here?

VHarisop
  • 3,840