1
$\begingroup$

thank you for viewing my question. I am trying to convert a symmetric pentadiagonal matrix to tridiagonal using givens rotation, but for now I can only think of a solution that is of order n^3 operations. I read somewhere that you can do this in order n^2.

intuitively I will think that the n^2 solution will make use of the fact a pentadiagonal matrix is sparse so that, for example, when left multiplying by the rotation matrix, we don't need to use the full ith row and jth row, because many columns in this sub-matrix are zero. However, what I don't get is that once I left multiply by the rotation matrix, some zero entries to the right (the columns to be visited in later iterations) will become non-zero. This means that this idea would not work.

My code is here:

% Loop to convert matrix using given rotations: It goes until half the
% length of the matrix because of the symmetry of the problem
for nj = 1:(N/2)    
    for ni = (2*nj+1):-1:(nj+2)
        if ni <= N
            % Determine the values of the given rotation to introduce a
            % zero in position (ni,nj)
            % G(ni,nj,theta) = [c  s ]T
            %                  [-s c ]
            [c, s] = given_rotations(T(ni-1,nj),T(ni,nj));

            % Multiply G*T
            T([ni-1,ni],:) = [c, -s; s, c]*T([ni-1,ni],:);

            % Multiply T*G'
            T(:,[ni-1,ni]) = T(:,[ni-1,ni])*[c, s; -s, c];
        end
    end
end

function [c, s] = given_rotations(a,b)
% Determine the values of the given rotation to introduce a
% zero in position (ni,nj)
% G(ni,nj,theta) = [c  s ]T
%                  [-s c ]
if b == 0
    c = 1; s = 0;
else
    if abs(b) > abs(a)
        r = -a/b;
        s = 1/sqrt(1+r^2);
        c = s*r;
    else
        r = -b/a;
        c = 1/sqrt(1+r^2);
        s = c*r;
    end
end

I know I must have some miss-conception, but I could of think of it. Could you please help me? Thank you very much.

$\endgroup$

closed as off-topic by JonMark Perry, zz20s, B. Goddard, GNUSupporter 8964民主女神 地下教會, José Carlos Santos Jan 9 '18 at 21:42

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is not about mathematics, within the scope defined in the help center." – JonMark Perry, zz20s, B. Goddard, GNUSupporter 8964民主女神 地下教會, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Hi if you know anyone who might know something about this, could you please forward this question, really appreciate it. $\endgroup$ – Joe Jan 9 '18 at 8:26
  • $\begingroup$ I think the answer in this question illustrates, what I am thinking. Basically, when you use givens rotation to rotate a tridiagonal or pentadiagonal matrix, you introduce additional non-zero super diagonals. $\endgroup$ – Joe Jan 9 '18 at 8:48
  • $\begingroup$ Hi, thank you very much. I have a question regarding your comment, how should I go about eliminating (i+2, i). I think I might be thinking wrong, but if say I am eliminating (i+2, i), then I could be introducing non-zero entries in another place like you described in the question I linked. I am wrong? Thank you very much. $\endgroup$ – Joe Jan 11 '18 at 7:28
  • $\begingroup$ True. It seems to be a bit more complicated. Let me think about it :-) $\endgroup$ – Algebraic Pavel Jan 11 '18 at 9:58
  • $\begingroup$ This is the Hessenberg reduction in case of a symmetric band matrix. Algorithm with complexity of order $O(n^2)$ can be found in Lapack's function DSBTRD.f. $\endgroup$ – Pawel Kowal Jan 11 '18 at 18:41