[Octave-bug-tracker] [bug #55751] scatter3 performance regression bug in Octave 5.0.91

[Eddy]

Follow-up Comment #15, bug #55751 (project octave):

Not sure if it is proper to post comment when the bug is marked "Fixed"...

@Markus
I tried several coplanar test methods. They all seems slightly faster than
your attached checker in comment 14 (file #46341).


N = 1e7;
[Q, ~] = qr(rand(3));           % random orthonormal matrix
vecs = rand(N, 2) * Q(1:2, :);  % random coplanar samples
disp(['Normal vector = ', num2str(Q(3, :))]);
[x, y, z] = deal(vecs(:,1), vecs(:,2), vecs(:,3));

tic; is_coplanar (x, y, z); toc

tic
[copl, normal_vector, eig_vals] = is_coplanar_lsm (x, y, z, [], 'svd');
toc

tic
[copl, normal_vector, eig_vals] = is_coplanar_lsm (x, y, z, [], 'eig');
toc

tic
[copl, normal_vector, eig_vals] = is_coplanar_lsm (x, y, z, [], 'lsm');
toc

octave-gui:>
Normal vector = -0.72582    -0.062478      0.68504
Elapsed time is 0.977858 seconds.
Elapsed time is 0.88521 seconds.
Elapsed time is 0.280604 seconds.
Elapsed time is 0.636894 seconds.


See attachment is_coplanar_lsm.m. There are 3 testers.

* 'svd': basically the one you are using in libinterp/corefcn/graphics.cc
* 'eig': mathematically equivalent to 'svd' method (svd(a).^2 <=> eig(a'*a)).
But instead of doing SVD of a very tall matrix, here only eigenvalue
factorization of 3x3 matrix is needed.
* 'lsm': find a planar by least square method, i.e. solve [a;b] in ax+by=z.

All of these methods have a clear geometric meaning of tolerance, namely
deviation to the best possible planar. In terms of FLOPS, 'lsm' method should
be the best, but in practice it is slower than 'eig'.

My feeling is, in order to get better performance, one need some heuristic or
greedy algorithm. e.g. first guess the correct planar by a set of good points,
then test if all other points are close enough to this planar.

(file #46348)
    _______________________________________________________

Additional Item Attachment:

File name: is_coplanar_lsm.m              Size:2 KB
    <https://savannah.gnu.org/file/is_coplanar_lsm.m?file_id=46348>



    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?55751>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/