Modify an algorithm to perform vector operations by eliminating the inner most for loop

Let A and B be square matrices (both stored column-wise) in R^{nxn} with B an Upper Triangular matrix. Write the MATLAB algorithm that gives C = A x B.

Here's my algorithm

function C = scalarMultRegUpper(A,B)
[n,n] = size(A);
[n,n]=size(B);
C=zeros(n,n);
for j=1:n
    for k=1:n
        for i=1:n
            C(i,j)=C(i,j) + B(k,j)*A(i,k);
        end
    end
end

Now, I'm asked to modify my algorithm to perform vector operations by eliminating the inner most for loop. How to do that? How will the algorithm change?

[Ameer Hamza]

What is the relevance of B being an Upper Triangular matrix? You are using the naive algorithm of matrix multiplication. I think you are expected to use a more efficient version for the upper triangular matrix B. Also, vectorizing these loops can simply be replaced with

C = A*B;

[Vladimir Sovkov]

The most fundamental and beatuful thing about Matlab (matrix laboratory) is that it supports matrix operations, so you can compute that product in just one line of code: C = A*B;

[Pascale Bou Chahine]

Exactly Ameer, what is the more efficient version to exploit the special structure of B, being triangular? What would the algorithm be?

[Ameer Hamza]

I am not sure what is an optimal algorithm for this case. It seems like a home problem. Have you studied something similar?

[Pascale Bou Chahine]

No, but how can I modify my algorithm to show the special property of B?

[Vladimir Sovkov]

If B is upper triangular, then B(k,j)=0 for k>(n+1-j) if the diagonal elements are nonzero (if they are zero, it is k>(n-j)). Hence in your code, you can restrict the k-loop to

for k=1:(n+1-j)

However anyway, C=A*B will work faster.

When working with big matrices having many zero elementss, using the sparse matrix format can be efficient, but I do not think it is justified for the triangular matrices; you can try it.

[Pascale Bou Chahine]

I tried running the algorithm with the modified k-loop as you suggested, and tried it for A = [3 2; 1 2], and B = [2 4; 0 4], and I got C = [6 12, 2 4]. However, C should be [6 20, 2 12]. What's the issue?

[Pascale Bou Chahine]

And what if both matrices, A and B, are upper triangular, how would this change my code?

[Vladimir Sovkov]

I implied that the upper triangular is the matrix of the form , while in your undestanding (maybe, more common) it is . This makes the things even easier:

for k=1:j

Rather obvious, isn't it?

[Pascale Bou Chahine]

Oh okay, thank you. And what would the algorithm be if both matrices were upper triangular (in my understanding)?

[Vladimir Sovkov]

Analogously. Analyze which elements of A are zero with every fixed k and exlude them from the loop over i. The product of upper triangular matrices is the upper triangular matrix.