Faster linear algebra in \

[dlfivefifty]

I just did Givens by hand, which slows down too much for large bandwidth. I'm sure this could be sped up by a large factor, either by using LA Pack on sub blocks, vectorization, or other tricks

[MikaelSlevinsky]

Here's an idea. Since Givens rotations involve only two rows at a time, if there are m nonzero diagonals below the main diagonal, then after a few starting rotations, m rotations zero-ing the anti-diagonal elements can be done "in parallel." With a vectorized givensreduceab! the number of function calls would decrease. The index of the bottom element would determine the data requirements, and the index of the top element would determine the stopping criterion. Once the stopping criterion is reached, a few "serial" Givens rotations polish it off.

[MikaelSlevinsky]

That should be "if there are m nonzero diagonals below the main diagonal, then after a few starting rotations, an alternation of floor(m/2) and ceil(m/2) rotations zero-ing the anti-diagonal elements can be done "in parallel.""

This would also reduce the calls to slnorm.

[dlfivefifty]

Hm not sure I understand, but maybe you mean row 1 eliminates row 2 while row 3 eliminates row 4 and row 5 eliminates row 6... Then once even rows are eliminated row 1 eliminates row 3 while row 5 eliminates row 7...

Could work. Though probably needs multi threading in julia (which is coming) and even then I don't have any experience in parallel so there could be memory issues.

There's probably research on this..

Sent from my iPhone

On 19 Dec 2014, at 12:58 pm, Richard Mikael Slevinsky notifications@github.com wrote:

Here's an idea. Since Givens rotations involve only two rows at a time, if there are m nonzero diagonals below the main diagonal, then after a few starting rotations, m rotations zero-ing the anti-diagonal elements can be done "in parallel." With a vectorized givensreduceab! the number of function calls would decrease. The index of the bottom element would determine the data requirements, and the index of the top element would determine the stopping criterion. Once the stopping criterion is reached, a few "serial" Givens rotations polish it off.

—
Reply to this email directly or view it on GitHub.

[MikaelSlevinsky]

I mean in the picture, first we zero A_{2,1} by A_{1,1}, then A_{3,1} is zeroed by the updated A_{1,1}.

Then the anti diagonals can be zero-ed simultaneously. A_{4,1} is zeroed by A_{1,1} while A_{3,2} is zeroed by A_{2,2}, and so on and so forth.

But I guess this is similar to doing it vertically as you suggested.

[MikaelSlevinsky]

Is there a reason Givens rotations are used instead of Householder transformations?

[dlfivefifty]

I'm under the impress that they are better for banded solves, but don't know why that would be

Sent from my iPhone

On 22 Dec 2014, at 9:28 am, Richard Mikael Slevinsky notifications@github.com wrote:

Is there a reason Givens rotations are used instead of Householder transformations?

—
Reply to this email directly or view it on GitHub.

[dlfivefifty]

The new implementation is much faster, so I'll close this issue. While its possible that it can be made even faster, it might be at the point of diminishing returns...