Matrix vs function for matrix operations

Admin 1
Viewed 142

Since I couldn't find anything about this subject, I decided to ask this question here. I am completely beginner and this question might be ridiculous.

Suppose we have A(NxN) matrix and a column vector (B(Nx1)). We have also a function f(i,j) that returns the element of the matrix A at row i and column j.

If we want to do some matrix operation, say, matrix product of A and B we can use: the following (below, C is the result of the matrix product) :

  1. using the function f(i,j): 
N = 100000


def f(i, j):
    return i + j


for i in range(N):
    for j in range(N):
        s = 0
        for k in range(N):
            s += f(i, k) * B[k]
        C[i] = s
  1. Using Matrix A (NxN) (suppose that A is already defined and contains the same elements returned by the function f)
N = 100000
for i in range(N):
     for j in range(N):
        s = 0
        for k in range(N):
            s += A[i,k]*B[k]
        C[i] = s

In my opinion, the advantage of the function is that it avoids storing all the values of the matrix thus saving the memory.

My questrions are:

  • In this case which is the most efficient way to do matrix multiplication (using the function or the matrix itself)?

  • Is there any performance difference between the two approaches?

EDIT: My question is not specific to Python or any other particular language.

matrix function performance
2 Answers

This honestly has no right answer since it depends on what you're willing to sacrifice and also on the language being used. Regardless, the main difference would be the function method would take more time than the matrix method, and the matrix method would take more space(obviously?).

Using time to save memory is generally not a good idea as we have an abundance of memory and a lot less of time.

I ran these in python with N=10 and got Function 0.015623331069946289, Matrix 0.0

N=100 and got Function 1.0839078426361084, Matrix 0.8769278526306152

~Currently running N=1000~

Anything larger and I'll have to switch to Numpy.

Here's the code I used to time it if anyone wants to try it out.

import time
n = 1000
def f(i, j):
  return i+j

A = [[i+j  for j in range(n)] for i in range(n)]
B = [i for i in range(n)]
C = [0 for _ in range(n)]

start1 = time.time()
for i in range(n):
  for j in range(n):
    s = 0
    for k in range(n):
      s += f(i, k) * B[k]
    C[i] = s
end1 = time.time()

start2 = time.time()
for i in range(n):
  for j in range(n):
    s = 0
    for k in range(n):
      s += A[i][k]*B[k]
    C[i] = s
end2 = time.time()


print("Function-", end1-start1, ", Matrix-", end2-start2)

Of course this approach assumes, as stated in your question, that the matrix is already set up, since that takes a significant amount of time to do too.

EDIT: Ran for N=1000, got Function 620.2477366924286, Matrix 478.4342918395996

As you can see, The larger it is the better time you'd receive with the matrix method

user_36323450

  1. You should not care about performance questions until you get performance issues. In 99.99% of cases - any approach will work for you. Code should be readable at first, and then performant About premature optimization

  2. In your concrete sample - code with function should be slower (just because of additional function call) or may have equal performance (if compiler will inline it). BTW - see #1 - you should not care and write readable code at first

  3. If you really need performant code - there are number of libraries for that (e.g. NumPy). Libraries will usually work faster. Some approaches may even delegate calculation to the GPU

Also see matrix multiplication performance

user_24284720
Related