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.