Is chol(...,"lower") significantly faster than default chol(...,"upper")?

[siko1056]

There is a small notice in the documentation of the chol-function, added in
2008:

  "In general the lower triangular factorization is significantly faster for
sparse matrices."

And I tried to verify this claim, using the small copy&paste sample:

%%%%%%%%%%%%%%%%%%%%%%%

NN = [2e0, 1e1, 5e1, 1e2, 5e2, 1e3];
t = zeros (4, length (NN));
for i = 1:length(NN)
  N = NN(i);
  A = rand (N, N);
  A = A + A' + N * eye (N);
  B = sprand (N, N, 1/N);
  B = B + B' + N * speye (N);
  # dry run
  [R, ~] = chol (A, "upper");
  tic;
  [R, ~] = chol (A, "upper");
  t(1, i) = toc;
  tic;
  [L, ~] = chol (A, "lower");
  t(2, i) = toc;
  tic;
  [R, ~] = chol (B, "upper");
  t(3, i) = toc;
  tic;
  [L, ~] = chol (B, "lower");
  t(4, i) = toc;
endfor

%{
figure; loglog (NN,t);
legend ({"dense upper", "dense lower", "sparse upper", "sparse lower"});
figure; plot (NN, t);
legend ({"dense upper", "dense lower", "sparse upper", "sparse lower"});
%}

disp (t)

%%%%%%%%%%%%%%%%%%%%%%%

The results on my computer are as follows:

dense A (upper and lower)
3.9101e-05   4.3154e-05   8.8930e-05   4.2987e-04   3.3204e-02   1.9014e-01
2.9087e-05   4.2915e-05   8.7976e-05   4.2486e-04   2.2402e-02   1.3919e-01

sparse B (upper and lower)
6.5088e-05   9.7036e-05   9.2983e-05   1.4615e-04   1.6081e-03   4.9210e-03
4.7922e-05   6.7949e-05   9.2030e-05   1.1492e-04   1.7529e-03   4.7388e-03

So I am a bit disappointed about the word "significant". The tendency for
"lower" to be a bit faster is given, but I would have expected more
significance, factor two or alike, to warn the user about this. Is there
something I missed, or is this observation out of date and might be removed?

Best,
Kai



--
View this message in context: 
http://octave.1599824.n4.nabble.com/Is-chol-lower-significantly-faster-than-default-chol-upper-tp4676859.html
Sent from the Octave - Maintainers mailing list archive at Nabble.com.