1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

Tags:
  1. Aug 28, 2014 #1
    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.

    1. The problem statement, all variables and given/known data
    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].

    2. Relevant 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 (Text):

    for i=1:n
      y(i) = a x(i) + y(i)
    end
     
    3. 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 (Text):

    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?
     
  2. jcsd
  3. Mar 1, 2015 #2
    Hi,

    did you do chapter 2?

    Best wishes.
     
  4. Mar 12, 2015 #3
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Matrix multiplication, P1.1.1 Golub/Van Loan-Matrix Computations 3rd
  1. Matrix Multiplication (Replies: 12)

  2. Matrix multiplication (Replies: 3)

  3. Matrix Multiplication (Replies: 3)

  4. Matrix multiplication (Replies: 5)

Loading...