LinearAlgebra

x<-rpois(1:10, lambda=40)
y<-rpois(1:10, lambda=10)
alpha<-.2
beta<-1.2

General

Detrmining Cost

• Remeber that size of vector (n) means the number of elements. Length of the vector is the euclidean length (a^2 + b^2) or square root of the sum of the squares of the components.
• Count floating point operations as Flops.
  • a multiplication or addition each costs 1 flop.

Vectors

• 1 dimensional arrof of n numbers is of size n
• ith number component
• start at 0
• in these cases, the location of the element \(\chi_i\) is relevent.
  • This is an ordered array.
• each element is \(\chi_i\) or \(\chi_i\in \mathbb{R}\)
• directions indicated by using an arrow.
  • \(\vec{\chi_i}\in \mathbb{R}\)
• length is given by the euclidean length. This is also called magnitude. Also called the two-norm.
  • \(\sqrt{\chi_0^2+\chi_1^2+...+\chi_{n-1}^2}\)
• vectors have no location.

Unit Basis Vectors

• \(\imath\)

---

Template ===================================

Operation name

Notes

• notes

Algorithm

• for i = 0 … n-1
  • \(n\)
• endfor

Cost

• memops
  • n
• flops -n

Example(s)

Functions

R

MatLab

---

Details

Addition

Notes

Algorithm

• for i = 0 … n-1
  • \(z_i:=\chi_i+\psi_i\)
• endfor

Cost

• Vector addtion and subtraction requires \(3n\) memops.
  • \(\chi\) is read, \(y\) is read, \(z\) (new vector) is written containing the results.
  • \(O(n)\)

Example(s)

Functions

R

lAddition<-function(x, y){
    z<-numeric(length(x));i<-1
    repeat{
        if((i-1)==length(x)){break}
        z[i]<-x[i]+y[i]
        i<-i+1
    }
    return(z)}
lAddition(rpois(1:10, lambda=70), rpois(1:10, lambda=20))

##  [1]  96  84  89  89  97  91  84  75 101  95

lVAdd<-function(x, y){
    vapply(1:length(x), function(i) x[i]+y[i], FUN.VALUE = numeric(1))}
lVAdd(rpois(1:10, lambda=70), rpois(1:10, lambda=20))

##  [1]  97  88  83  88  94  83 100 100  86  89

MatLab

Subraction

Notes

Algorithm

• for i = 0 … n-1
  • \(z_i:=\chi_i+(-\psi_i)\)
• endfor

Cost

• Vector addtion and subtraction requires \(3n\) memops.
  • \(\chi\) is read, \(y\) is read, \(z\) (new vector) is written containing the results.
  • \(O(n)\)

Example(s)

Functions

R

lSubtraction<-function(x, y){
    z<-numeric(length(x));i<-1
    repeat{
        if((i-1)==length(x)){break}
        z[i]<-x[i]-y[i]
        i<-i+1}
    return(z)}
lSubtraction(rpois(1:10, lambda=70), rpois(1:10, lambda=20))

##  [1] 51 57 42 61 29 50 41 53 39 53

lVSubtract<-function(x, y){
    vapply(1:length(x), function(i) x[i]-y[i], FUN.VALUE = numeric(1))}
lVSubtract(rpois(1:10, lambda=70), rpois(1:10, lambda=20))

##  [1] 51 48 40 53 39 40 50 56 39 57

MatLab

Scaling

Notes

Algorithm

• for i = 0 … n-1
  • \(z_i:=\alpha*\chi_i\)
• endfor

Cost

• Vector scaling requires \(n\) flops and \(2n+1\) memops.
  • \(\alpha\) is only looked up from memory once.
  • \(\chi\) is read, and new vector is written such that \(((\chi_i*\alpha) := z_i)\times n\). This yields a memop of \(2n\).

Example(s)

Functions

R

lScaling<-function(x, alpha){
    z<-numeric(length(x));i<-1
    repeat{
        if((i-1)==length(x)){break}
        z[i]<-x[i]*alpha
        i<-i+1}
    return(z)}
lScaling(rpois(1:10, lambda=70), 2.2)

##  [1] 158.4 136.4 149.6 162.8 154.0 173.8 147.4 143.0 173.8 173.8

lVScale<-function(x, alpha){
    vapply(1:length(x), function(i) x[i]*alpha, FUN.VALUE = numeric(1))}
lVScale(rpois(1:10, lambda=70), 2.2)

##  [1] 178.2 154.0 162.8 145.2 132.0 162.8 134.2 143.0 158.4 154.0

MatLab

AXPY (Scaled vector Addition)

Notes

Algorithm

• for i=0, …, i=n-1
  • \(z_i := (\chi_i\times\alpha) + \psi_i\)
• end for

Cost

• \(\alpha\) is only looked up once. \(+1\)
• \((\chi\times n) + (\psi\times n) + 1\)
  • memops = \(3n +1\)
  • flops = \(2n\)

Example(s)

Functions

R

lAXPY<-function(x, y, alpha){
    z<-numeric(length(x));i<-1
    repeat{
        if((i-1)==length(x)){break}
        z[i]<-(x[i]*alpha)+y[i]
        i<-i+1}
    return(z)}
lAXPY(rpois(1:10, lambda=70),rpois(1:10, lambda=10), 2.2)

##  [1] 145.0 152.8 144.6 168.4 171.6 201.2 147.2 139.8 182.2 184.2

lVAXPY<-function(x, y, alpha){
    vapply(1:length(x), function(i) (x[i]*alpha)+y[i], FUN.VALUE = numeric(1))
}
lVAXPY(rpois(1:10, lambda=70),rpois(1:10, lambda=10), 2.2)

##  [1] 186.4 178.4 170.0 149.8 156.4 145.0 164.0 181.2 166.2 143.2

MatLab

Linear Cominations of Vectors

Notes

• \(\sum\limits_{i=0}^{n-1} \chi_i \times e_1\)

Algorithm

• w = 0
• for j=0, …, i=n-1
  • \(w := \chi_j \times v_j + w\)
• end for

Cost

Example(s)

Functions

R

lCombinations<-function(x, y, alpha=1, beta=1){
    w<-0 # w is our running sum
    for(j in seq(from=1, to=length(x))){
        w<-w+((x[j]*alpha)+(y[j])*beta)
    }
    return(w)
}
lCombinations(x, y, alpha, beta)

## [1] 196.4

lVComb<-function(x, y, alpha=1, beta=1){
    sum(vapply(1:length(x), function(j) ((x[j]*alpha)+(y[j])*beta), FUN.VALUE = numeric(1)))
}
lVComb(x, y, alpha, beta)

## [1] 196.4

MatLab

Dotproduct

Notes

• Also refered to as the Inner Product
• defined by
  • dot\((x,y) = [\sum\limits_{i=0}^{n-1} \chi_i \times \psi_i] = [\chi_0 \times \psi_0 + \chi_1 \times \psi_1 + ... + \chi_{n-1} \times \psi_{n-1}]\)
• often writen as
  • \(x^ty = dot(x,y)\)
    • \(= \begin{bmatrix} \chi_{0} \\ \chi_{1} \\ ... \\ \chi_{n-1} \end{bmatrix} ^t \begin{bmatrix} \psi_{0} \\ \psi_{1} \\ ... \\ \psi_{n-1} \end{bmatrix}\)
    • \(= (\chi_0, \chi_1, ... \chi_{n-1}) \times \begin{bmatrix} \psi_{0} \\ \psi_{1} \\ ... \\ \psi_{n-1} \end{bmatrix}\)
    • \(= (\chi_0 \times \psi_0) + (\chi_1 \times \psi_1) + (...) + (\chi_{n-1} \times \psi_{n-1})\)

Algorithm

Note that in this algorithm, \(\alpha\) is our running sum.

• \(\alpha := 0\)
• for i=0, …, n-1
  • \(\alpha := (\chi_i \times \psi_i) + \alpha\)
• endfor

Cost

Example(s)

Functions

R

lDotProduct<-function(x, y){
    alpha<-0 # alpha is our running sum
    for(i in seq(from=1, to=length(x))){
        alpha<-(x[i]*y[i])+alpha
    }
    return(alpha)
}
lDotProduct(x, y)

## [1] 3843

MatLab

Vector Length

Notes

• \(||\chi||\) stands for the 2 norm of \(\chi\) which is simply another way of saying the length of \(\chi\)
• A vector of length one is said to be a unit vector.
• \(||\chi|| = \sqrt{\sum\limits_{i=0}^{n-1} \chi_i^2}\)

Algorithm

• \(||x||_2 = \sqrt{\chi^t \chi}\)

Cost

• memops
  • \(n\)
• flops
  • \(2n\)

Example(s)

Functions

R

lLength<-function(x){
    z<-0
    for(i in seq(from=1, to=length(x))){
        z<-(x[i])^2+z
    }
    return(sqrt(z))
}
lLength(c(1,2,5,0,1)) # sum 9, sq 31, sqrt 5.567764

## [1] 5.567764

MatLab

Vector Function (Vector Valued Functions)

Notes

• Think of a scaler as a vectore of length 1.
• \(f\) takes in one or more scalers and/or vectors and outputs a vector.
• Also equal to the square root of the dot product of the vector with itself.
  • dotproduct of X transposed times X

sqrt(sum(c(1,5,6,1) * t(c(1,5,6,1))))

## [1] 7.937254

• It is important to note that these are all the same thing.
  • The lLength is equal to the square root of the X and Transpose X which is also equal to the square root of the dot product of x and transpose x.

lLength(c(1,5,6,1)) == sqrt(sum(c(1,5,6,1) * t(c(1,5,6,1)))) & lLength(c(1,5,6,1))  == sqrt(lDotProduct(c(1,5,6,1), t(c(1,5,6,1))))

## [1] TRUE

Algorithm

• for i = 0 … n-1
  • \(n\)
• endfor

Cost

• memops
  • \(n\)
• flops
  • \(2n\)

Example(s)

• \(f(\alpha, \beta) = \begin{bmatrix} \alpha + \beta \\ \alpha - \beta \end{bmatrix}\)

Example(s)

Functions

R

MatLab

Vector Function (Vector -> Vector)

Notes

• notes

Algorithm

• for i = 0 … n-1
  • \(n\)
• endfor

Cost

• memops
  • n
• flops -n

Example(s)

• \(f(\alpha, \begin{bmatrix} \chi_0 \\ \chi_1 \end{bmatrix}) = \begin{bmatrix}\chi_0 + \alpha \\ \chi_1 + \alpha \end{bmatrix}\)

Example(s)

Functions

R

MatLab

---

---