Faster linear algebra in \ about approxfun.jl HOT 7 CLOSED

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.

from approxfun.jl.

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.

from approxfun.jl.

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 [email protected] 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.

from approxfun.jl.

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.

from approxfun.jl.

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

from approxfun.jl.

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 [email protected] wrote:

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

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

from approxfun.jl.

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...

from approxfun.jl.