Matrix multiplication, P1.1.1 Golub/Van Loan-Matrix Computations 3rd

[nanoship]

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.

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.

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
$$A=\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}, \; B=\begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix}$$
then fırst column of $C=\begin{bmatrix} c_1 & c_2 \end{bmatrix}$ (column partitioned) is
$$c_1=\begin{bmatrix} 1 \\ 3 \end{bmatrix}5 + \begin{bmatrix} 2 \\ 4 \end{bmatrix}7$$
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.

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?

 

[ero1981]

Hi,

did you do chapter 2?

Best wishes.

 

[nanoship]

Hi,

Unfortunately I didn't. I switched to a book with a solution manual as I don't like solving problems without knowing if they are true or not.