Question

Compute the approximate number of basic arithmetic operations required to do the following operations. Explain your thinking in each case. 1. Compute the dot product of two vectors in R n . 2. Compute Ax for A ∈ R m×n and x ∈ R n . 3. Compute kAxk2 for A ∈ R m×n and x ∈ R n . 4. Compute AB for A ∈ R m×n and B ∈ R n×k . 5. Compute the QR factorization of A in R m×n . 6. Solve Rx = b where R ∈ R n×n is upper triangular.

Answer 1

1)dot product of two vectors x belongs to Rn

will require n multiplications and n-1 additions

total 2n-1 basic arithematic operations

2)Scalar multiplication of matrix m*n

each element in matrix need to be multiplied by scalar

= no of elements in matrix , multiplications are required

=mn

3)Ax requires m(2n-1),

as each row in A requires n multiplications and n-1 additions

and there are m rows , so total basic arithematic operations are m(2n-1)

4)AB , A is m*n and B is n*k

let AB = C , C will be m*k

for getting each element of c we need to do n multiplications and n-1 additions = 2n-1 operations

As there are mk elements in C , total operations are mk(2n-1)