- #1
nanoship
- 2
- 0
Hi,
I am studying linear algebra from Golub G.H., Van Loan C.F.- Matrix Computations 3rd edition. This book is somewhat old now, but I find it rather comprehensive. I want to study all chapters and answer all problems appear at the end of each section. Here is the first problem from the first section. I found a solution but I am not sure if that is the right one.
Suppose [itex] A \in \mathbb{R}^{n\times n}[/itex] and [itex]x \in \mathbb{R}^{r} [/itex] are given. Give a saxpy algorithm for computing the first column of [itex] M=(A-x_{1}I) \dots (A-x_{r}I)[/itex].
saxpy operation updates a vector ##y## by a scalar-vector multiplication. It is the shorthand for "scalar a x plus y". If [itex] x,y \in \mathbb{R}^{n} [/itex] and [itex] a \in \mathbb{R} [/itex], then saxpy algorithm can be written as below.
For this problem I propose a generalized solution. I suppose ##M## is multiplication of ##r## arbitrary matrices.
Consider matrix multiplication ##C=AB##.
Any column of ##C## can be written as a linear combination of the columns of ##A##. For example, if
[tex]A=\begin{bmatrix}
1 & 2 \\
3 & 4
\end{bmatrix},
\;
B=\begin{bmatrix}
5 & 6 \\
7 & 8
\end{bmatrix}
[/tex]
then fırst column of [itex] C=\begin{bmatrix} c_1 & c_2 \end{bmatrix} [/itex] (column partitioned) is
[tex]
c_1=\begin{bmatrix}
1 \\
3
\end{bmatrix}5 +
\begin{bmatrix}
2 \\
4
\end{bmatrix}7
[/tex]
Note that calculation of ##c_1## involves ##A## as a whole but only the first column of ##B##.
Taking [itex] A^i=(A-x_iI)[/itex], ##M## can be written as follows.
[itex]M=A^1*A^2 \cdots A^{r-1}*A^r,\quad A^r=\begin{bmatrix} c_1^r & c_2^r & \cdots & c_n^r \end{bmatrix}[/itex]
We can find the first column of ##M## by calculating the first column of the rightmost multiplication at each step. Below I made a list of calculations. Note that first column of the left matrix of the rightmost multiplication is updated at each step.
1.step: ##m_1=A^1*A^2 \cdots A^{r-1}*c_1^r,\quad c_1^{r-1}=A^{r-1}c_1^r##
2.step: ##m_2=A^1*A^2 \cdots A^{r-2}*c_1^{r-1},\quad c_1^{r-2}=A^{r-2}c_1^{r-1}##
##\vdots##
r-1.step: ##M=A^1*c_1^2##
I provide the octave code I have written for this algorithm below. Here, saxpy operations occupy the inner loop.
My question is: Is there a faster way of calculating ##c_1## for the [itex]\prod^{r}_{i=1}{(A-x_{i}I)}[/itex] case?
I am studying linear algebra from Golub G.H., Van Loan C.F.- Matrix Computations 3rd edition. This book is somewhat old now, but I find it rather comprehensive. I want to study all chapters and answer all problems appear at the end of each section. Here is the first problem from the first section. I found a solution but I am not sure if that is the right one.
Homework Statement
Suppose [itex] A \in \mathbb{R}^{n\times n}[/itex] and [itex]x \in \mathbb{R}^{r} [/itex] are given. Give a saxpy algorithm for computing the first column of [itex] M=(A-x_{1}I) \dots (A-x_{r}I)[/itex].
Homework Equations
saxpy operation updates a vector ##y## by a scalar-vector multiplication. It is the shorthand for "scalar a x plus y". If [itex] x,y \in \mathbb{R}^{n} [/itex] and [itex] a \in \mathbb{R} [/itex], then saxpy algorithm can be written as below.
Code:
for i=1:n
y(i) = a x(i) + y(i)
end
The Attempt at a Solution
For this problem I propose a generalized solution. I suppose ##M## is multiplication of ##r## arbitrary matrices.
Consider matrix multiplication ##C=AB##.
Any column of ##C## can be written as a linear combination of the columns of ##A##. For example, if
[tex]A=\begin{bmatrix}
1 & 2 \\
3 & 4
\end{bmatrix},
\;
B=\begin{bmatrix}
5 & 6 \\
7 & 8
\end{bmatrix}
[/tex]
then fırst column of [itex] C=\begin{bmatrix} c_1 & c_2 \end{bmatrix} [/itex] (column partitioned) is
[tex]
c_1=\begin{bmatrix}
1 \\
3
\end{bmatrix}5 +
\begin{bmatrix}
2 \\
4
\end{bmatrix}7
[/tex]
Note that calculation of ##c_1## involves ##A## as a whole but only the first column of ##B##.
Taking [itex] A^i=(A-x_iI)[/itex], ##M## can be written as follows.
[itex]M=A^1*A^2 \cdots A^{r-1}*A^r,\quad A^r=\begin{bmatrix} c_1^r & c_2^r & \cdots & c_n^r \end{bmatrix}[/itex]
We can find the first column of ##M## by calculating the first column of the rightmost multiplication at each step. Below I made a list of calculations. Note that first column of the left matrix of the rightmost multiplication is updated at each step.
1.step: ##m_1=A^1*A^2 \cdots A^{r-1}*c_1^r,\quad c_1^{r-1}=A^{r-1}c_1^r##
2.step: ##m_2=A^1*A^2 \cdots A^{r-2}*c_1^{r-1},\quad c_1^{r-2}=A^{r-2}c_1^{r-1}##
##\vdots##
r-1.step: ##M=A^1*c_1^2##
I provide the octave code I have written for this algorithm below. Here, saxpy operations occupy the inner loop.
Code:
function c1 = pr111(n,r)
A = magic(n)
x = round(rand(r,1)*100) # r-vector of elements in the range [0 100] integers
Ar = cell(r,1);
for i=1:r
Ar{i} = A-eye(n)*x(i);
end
for i=r:-1:2
y=zeros(n,1);
# calculate the first column of rightmost multiplication
for j=1:n
y = Ar{i-1}(:,j)*Ar{i}(j,1) + y;
end
# update the first column of left matrix
Ar{i-1}(:,1) = y;
end
c1 = Ar{1}(:,1);
My question is: Is there a faster way of calculating ##c_1## for the [itex]\prod^{r}_{i=1}{(A-x_{i}I)}[/itex] case?