- #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 A \in \mathbb{R}^{n\times n} and x \in \mathbb{R}^{r} are given. Give a saxpy algorithm for computing the first column of M=(A-x_{1}I) \dots (A-x_{r}I).
saxpy operation updates a vector ##y## by a scalar-vector multiplication. It is the shorthand for "scalar a x plus y". If x,y \in \mathbb{R}^{n} and a \in \mathbb{R}, 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
A=\begin{bmatrix}<br /> 1 & 2 \\<br /> 3 & 4<br /> \end{bmatrix},<br /> \;<br /> B=\begin{bmatrix}<br /> 5 & 6 \\<br /> 7 & 8<br /> \end{bmatrix}<br />
then fırst column of C=\begin{bmatrix} c_1 & c_2 \end{bmatrix} (column partitioned) is
<br /> c_1=\begin{bmatrix}<br /> 1 \\<br /> 3<br /> \end{bmatrix}5 +<br /> \begin{bmatrix}<br /> 2 \\<br /> 4<br /> \end{bmatrix}7<br />
Note that calculation of ##c_1## involves ##A## as a whole but only the first column of ##B##.
Taking A^i=(A-x_iI), ##M## can be written as follows.
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}
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 \prod^{r}_{i=1}{(A-x_{i}I)} 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 A \in \mathbb{R}^{n\times n} and x \in \mathbb{R}^{r} are given. Give a saxpy algorithm for computing the first column of M=(A-x_{1}I) \dots (A-x_{r}I).
Homework Equations
saxpy operation updates a vector ##y## by a scalar-vector multiplication. It is the shorthand for "scalar a x plus y". If x,y \in \mathbb{R}^{n} and a \in \mathbb{R}, then saxpy algorithm can be written as below.
Code:
for i=1:n
y(i) = a x(i) + y(i)
endThe 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
A=\begin{bmatrix}<br /> 1 & 2 \\<br /> 3 & 4<br /> \end{bmatrix},<br /> \;<br /> B=\begin{bmatrix}<br /> 5 & 6 \\<br /> 7 & 8<br /> \end{bmatrix}<br />
then fırst column of C=\begin{bmatrix} c_1 & c_2 \end{bmatrix} (column partitioned) is
<br /> c_1=\begin{bmatrix}<br /> 1 \\<br /> 3<br /> \end{bmatrix}5 +<br /> \begin{bmatrix}<br /> 2 \\<br /> 4<br /> \end{bmatrix}7<br />
Note that calculation of ##c_1## involves ##A## as a whole but only the first column of ##B##.
Taking A^i=(A-x_iI), ##M## can be written as follows.
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}
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 \prod^{r}_{i=1}{(A-x_{i}I)} case?
