Thread Subject:

Speedup mldivide for repeated calls with same matrix

Hi,

I have a huge matrix A and some data vectors bi and want to repeatedly
(100-1000 times) solve the problem A * xi = bi
Of course I am using mldivide:
xi = A \ bi

Now I wanted to speed this up and wanted to know if I could precompute
the part of A \ bi that does not depend on bi (some kind of
factorization probably). However I did not find any good information how
mldivide works internally.

How do I do it? I.e. what does mldivide compute?
and
Is it worth it? I.e. how much time in A \ bi is spent on A only?

One additional difficulty: A can be sparse. A \ bi works also fine for
sparse matrices but it might be that this makes the whole thing more
difficult.

Cheers
Jan

"Jan" <jkeller1@gwdg.de> wrote in message
news:jt2a3o$1ru0$1@gwdu112.gwdg.de...
> Hi,
>
> I have a huge matrix A and some data vectors bi and want to repeatedly
> (100-1000 times) solve the problem A * xi = bi
> Of course I am using mldivide:
> xi = A \ bi

Remember that b doesn't need to be a vector, it can be a matrix. Create a
matrix B where each column is one of your b's and solve X = A\B, then
extract the appropriate column of X.

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Thank you. That helped a lot. I tested it and saw that for my case (a
260e3x14e3 matrix) the time spent on matrix A alone is roughly five
times larger than the part spent on any column of B. I measured the time
per column for increasing numbers of columns in B and then assumed that
the total time is tA + n * tB where tA is the time spent on A alone and
tB the time spent on a single column of B and n the number of columns. A
code fragment doing this is attached.

The memory consumption is somewhat increased though.

Also important is that I reached almost all the speed increase already
for >=10 columns. I wanted to additionally parallelize the algorithm
(having 4 or even 8 cores nowadays on a single CPU). mldivide seems to
be not parallelized internally. But I can work with chunks of columns
and using a parfor loop.

It would be nice if mldivide would be parallelized internally in a
future version of MatLab.

Thanks again.

---------------

% solve M * x = bi for all columns bi of b
close all;
figure;
hold on;
n = size(b, 2);
res = zeros(n,1);
% loop and measure time per column
for ki = 1 : n
     tic;
     est = M \ b(:, 1:ki);
     t = toc;
     res(ki) = t / ki;
     plot(ki, r(ki), 'bo');
     drawnow
end;
% fit and plot
xi = (1:n)';
fun = @(x, d) 1./d * x(1) + x(2);
x = lsqcurvefit(fun, [max(r) - min(r), min(r)], xi, res);
plot(xi, fun(x, xi), 'r-');


On 7/5/2012 5:14 AM, Steven_Lord wrote:
>> I have a huge matrix A and some data vectors bi and want to repeatedly
>> (100-1000 times) solve the problem A * xi = bi
>> Of course I am using mldivide:
>> xi = A \ bi
>
> Remember that b doesn't need to be a vector, it can be a matrix. Create
> a matrix B where each column is one of your b's and solve X = A\B, then
> extract the appropriate column of X.
>