2

Let v be a row vector of length n. The goal is to create a matrix A with m rows that are all equal to v.

MATLAB has a function for this that is called repmat. Possible code would be

A = repmat(v,[m 1])

There is an alternative equally concise way using simple matrix operations

A = ones(m,1)*v

Is any of the two methods preferable for large m and n?

Wolpertinger
  • 1,169
  • 2
  • 13
  • 30

2 Answers2

3

Lets compare them!

When testing algorithms 2 metrics are important: time, and memory.

Lets start with time:

enter image description here

Clearly repmat wins!

Memory:

profile -memory on
for m=1000:1000:50000
f1=@()(repmat(v,[m 1]));
f2=@()(ones(m,1)*v);
ii=ii+1;
t1(ii)=timeit(f1);
t2(ii)=timeit(f2);
end
profreport

enter image description here

It seems that both take the same amount of memory. However, the profiler is known for not showing all the memory, so we can not fully trust it.

Still, it is clear that repmat is better

Ander Biguri
  • 35,140
  • 11
  • 74
  • 120
2

You should use repmat().

Matrix Multiplication is O(n ^ 3) operation which is much slower then replicating data in memory.
On top of that, the second option allocate more data in memory of the size of the output.

In the case above you create a vector which the outer multiplication is faster yet still not as memory operation.

MATLAB doesn't use the knowledge all vector elements are 1, hence you multiply each element of x by 1 m times.

Both operations will be mainly memory bounded, yet more efficient, fast and direct method would be going with repmat().

The question is, what you do afterwards?
Because you may not need repmat().

Royi
  • 4,640
  • 6
  • 46
  • 64
  • 1
    "Matrix Multiplication is O(n ^ 3)". *Your* matrix multiplication is that slow, not MALTABs. – Ander Biguri Mar 30 '17 at 12:15
  • Matrix multiplication is O(n^3) operation (In general, there are cases which is faster, for instance circulant matrices or symmetric matrices, etc...). No code can change that. MATLAB has efficient implementation which minimizes the constant not the Asymptotic Behavior. – Royi Mar 30 '17 at 12:20
  • `On modern architectures with hierarchical memory, the cost of loading and storing input matrix elements tends to dominate the cost of arithmetic. On a single machine this is the amount of data transferred between RAM and cache, while on a distributed memory multi-node machine it is the amount transferred between nodes; in either case it is called the communication bandwidth. The naïve algorithm using three nested loops uses Ω(n3) communication bandwidth.` I can tell you this is what is being done in all BLAS packages for arbitrary matrices. – Royi Mar 30 '17 at 12:27
  • There is OpenBLAS, can you find there implementation which they state is lower then O(n ^ 3)? – Royi Mar 30 '17 at 12:28
  • 1
    https://stackoverflow.com/questions/6058139/why-is-matlab-so-fast-in-matrix-multiplication. Answerer is a Mathworks employee. – Ander Biguri Mar 30 '17 at 12:30
  • 1
    You better read here: http://stackoverflow.com/questions/17716565/matrix-multiplication-time-complexity-in-matlab You'll see that those methods are not practical. Intel MKL is O(n ^ 3) algorithm with the best utilization of memory bandwidth and cache coherency but it is still O(n ^ 3). – Royi Mar 30 '17 at 12:34
  • You may be right, that answer hints otherwise. However that would make a Mathworks employee wrong, and I doubt that. – Ander Biguri Mar 30 '17 at 12:35
  • It has nothing to do with MathWorks employee as the matrix multiplication in MATLAB is based on Intel's MKL. In practice all methods are limited by Memory Bandwidth. Hence the biggest factor for the actual performance is keeping data locality. And the bet known algorithm for that is O(n ^ 3) as you can see in the link above. – Royi Mar 30 '17 at 12:38
  • 1
    The only way around it is look for special properties of the matrix and execute a specialized operation for that (Indeed MATLAB does this). – Royi Mar 30 '17 at 12:44
  • You welcome. We all here to share and absorb knowledge. Thank You. – Royi Mar 30 '17 at 12:48
  • 1
    O(n^3) is multiplying two nxn matrices. Multiplying two vectors of size n and m is obviously an operation that takes exactly n*m multiplications. – Cris Luengo May 27 '19 at 16:56