subroutine tridcf (n, is, t1, t2, tt) c-----------------------------------------------------------------------* c Cyclic reduction for solving the tridiagonal system T x = z, where T * c is symmetric positive definite and tridiagonal. This is the reduction * c part of the cyclic reduction method. To solve a system, first call * c tridcf then follow it by a call to tridcs for each system to solve. * c warning: the matrices t1, t2, and tt should not be modified between * c the successive calls to tridcs. * c-----------------------------------------------------------------------* c argument list: * c input : * c n = integer equal to the dimension of the problem. * c is = number of cyclic reduction steps to be taken. If the value of * c is is negative of if 2**is+1 exceeds n then the code chooses * c a default value. * c t1 = real*8 array of size n, containing the subdiagonal of T * c t2 = real*8 array of size n containing the diagonal matrix * c The nonzero elements of T are stored in t1, t2, with t1 starting* c in position 2. * c tt = real*8 array of size at least 3*n + log2(n), used to store the* c pivot information during the elimination process. * c output: * c t1, t2, and tt are filled with the reduction transormations * c WARNING THIS CODE DOES NOT INTERCHANGE rows or colums in case of small* c pivots. If the matrix is not positive definite problems may arise. * c-----------------------------------------------------------------------* real*8 t1(n), t2(n), tt(n), dpiv c------------------------------------------------------------- c chose alternate value for is if the one given is not valid. k = log2c(n) if (is .ge. 0 .and. is .le. k) goto 10 c--------- this choice is based on vectorization only -------- c (stop reducing when vector length is less than 16) -------- is = max0(0,k-4) c------------------------------------------------------------- c begin reduction loop --------------------------------------- c------------------------------------------------------------- tt(1:n-1) = t1(2:n) 10 k = n ioff1 = 1 do 21 j=1, is ioff0 = ioff1 ioff1 = ioff1 + ioff1 i0 = ioff1+1 i1 = i0-ioff0 i2 = n - ioff0 k0 = k +1 k = k + ((n-1)/ioff1+1) c keep diagonal in inverted form CVD$ NOSYNC t2(i1:n:ioff1) = 1.0d0 / t2(i1:n:ioff1) c c compute pivots. First = lower part, second = upper part. c CVD$ NOSYNC tt(k0:k) = t1(i0:n:ioff1) * t2(i1:i2:ioff1) CVD$ NOSYNC t2(i0:n:ioff1) = t2(i0:n:ioff1) - tt(k0:k)*t1(i0:n:ioff1) k1 = n+n+is+k0 k2 = n+n+is+k CVD$ NOSYNC tt(k1:k2) = t1(i1:n:ioff1) * t2(i1:n:ioff1) CVD$ NOSYNC t2(1:i2:ioff1)=t2(1:i2:ioff1)-tt(k1:k2)*t1(i1:n:ioff1) CVD$ NOSYNC t1(i0:n:ioff1) = -t1(i1:i2:ioff1)*tt(k0:k) tt(1:i2:ioff1) = t1(i0:n:ioff1) 21 continue c------------------------------------------------------------- c 1) forward sweep c------------------------------------------------------------- k = 1 22 t2(k) = 1.0d0 / t2(k) k = k+ioff1 dpiv = t1(k)*t2(k-ioff1) t2(k) = (t2(k) - dpiv*t1(k)) t1(k) = dpiv if (k+ioff1 .le. n) goto 22 t2(k) = 1.0d0 / t2(k) return end c---------------------------------------------------------------------- subroutine tridcs (n, is, t1, t2, tt, z) c-----------------------------------------------------------------------* c Cyclic reduction for solving the tridiagonal system T x = z, where T * c is a symmetric and tridiagonal matrix. This subroutine performs the * c solution part and assumes that the arrays t1, t2, and tt have been * c processed by tridcf. To solve a system, first call tridcf, then * c follow it by a call to tridc2 for each system to solve. * c Warning: the matrices t1, t2, and tt should not be modified between * c the successive calls to tridcs. * c-----------------------------------------------------------------------* c Argument list: * c input : * c n = integer equal to the dimension of the problem. * c is = number of reduction steps to be taken. Same as in tridcf. * c t1 = real*8 array of size n, containing the subdiagonal of T as * c modified by tridcf * c t2 = real*8 array of size n containing the diagonal matrix of T as * c modified by tridcf * c z = real*8 array of size n containing the right hand side. * c tt = real*8 array of size at least 3*n + log2(n), the elements of * c which are produced by tridcf. * c output: * c z is replaced by the solution to the system * c-----------------------------------------------------------------------* real*8 t1(n), t2(n), z(n), tt(n), dpiv c-----------------------------------------------------------------------* k = n ioff1 = 1 do 21 j=1, is ioff0 = ioff1 ioff1 = ioff1 + ioff1 i0 = ioff1+1 i1 = i0-ioff0 i2 = n - ioff0 k0 = k +1 k = k + ((n-1)/ioff1 +1) k1 = n+n+is+k0 k2 = n+n+is+k c do the forward transformation CVD$ NOSYNC z(i0:n:ioff1) = z(i0:n:ioff1)-tt(k0:k)*z(i1:i2:ioff1) c do the backward transformation CVD$ NOSYNC z(1:i2:ioff1) = z(1:i2:ioff1)-tt(k1:k2)*z(i1:i2:ioff1) 21 continue c------------------------------------------------------------- c solve residual tridiagonal system ----- c 1) forward sweep c------------------------------------------------------------- k = 1 22 k = k+ioff1 z(k) = z(k) - t1(k)*z(k-ioff1) if (k+ioff1 .le. n) goto 22 z(k) = z(k) * t2(k) c 2) backward sweep 23 k = k -ioff1 z(k) = (z(k) - tt(k)*z(k+ioff1))*t2(k) if (k .gt. ioff1) goto 23 c------------------------------------------------------------- c---- finally solve " even equations " ----------------------- c------------------------------------------------------------- do 24 j=1, is ioff0 = ioff1/2 i0 = ioff0+1 i2 = n - ioff0 i3 = ioff1 + 1 CVD$ NOSYNC z(i0:n:ioff1)=(z(i0:n:ioff1)-t1(i0:n:ioff1)*z(1:n:ioff1) - * tt(i0:n:ioff1)*z(i3:n:ioff1))*t2(i0:n:ioff1) ioff1 = ioff0 24 continue return end c---------------------------------------------------------------------- subroutine tridcf2 (n, is, t1, t2, t3, tt) c-----------------------------------------------------------------------* c Cyclic reduction for solving the tridiagonal system T x = z, where T * c is nonsymmetric diagonally dominant & tridiagonal. This is the * c reduction part of yclic reduction method to solve a nonsymmetric tri- * c diagonal linear system of equations. To solve a system, first call * c tridcf2 then follow it by a call to tridcs2 for each system to solve. * c warning: the matrices t1, t2, t3, tt should not be modified between * c the successive calls. ns should also be the same * c-----------------------------------------------------------------------* c argument list: * c input : * c n = integer equal to the dimension of the problem. * c is = number of cyclic reduction steps to be taken. If the value of * c is is negative of if 2**is+1 exceeds n then the code chooses * c a default value. * c t1 = real*8 array of size n, containing the subdiagonal of T * c t2 = real*8 array of size n containing the diagonal matrix * c t3 = real*8 array of size n containing the super-diagonal of T * c The nonzero elements of T are stored in t1, t2, t3 in such a way* c that t1(i), t2(i), t3(i) are the nonzero elements of the i-th * c row of T. t1(1) and t3(n) are never used. * c z = real*8 array of size n containing the right hand side. * c tt = real*8 array of size at least 2*n + log2(n), used to store the* c pivot information during the elimination process. * c output: * c t1, t2, and t3 are replaced by the transformed diagonals. * c tt is filled with pivot information to be used by tridcs2 * c WARNING THIS CODE DOES NOT INTERCHANGE rows or colums in case of small* c pivots. If the matrix is not diagonally dominant problems may arise * c-----------------------------------------------------------------------* real*8 t1(n), t2(n), t3(n), tt(n), dpiv c------------------------------------------------------------- c chose alternate value for is if the one given is not valid. k = log2c(n) if (is .ge. 0 .and. is .le. k) goto 10 c--------- this choice is based on vectorization only -------- c (stop reducing when vector length is less than 16) -------- is = max0(0,k-4) c------------------------------------------------------------- c begin reduction loop --------------------------------------- c------------------------------------------------------------- 10 k =0 ioff1 = 1 do 21 j=1, is ioff0 = ioff1 ioff1 = ioff1 + ioff1 i0 = ioff1+1 i1 = i0-ioff0 i2 = n - ioff0 k0 = k +1 k = k + ((n-1)/ioff1+1) c keep diagonal in inverted form CVD$ NOSYNC t2(i1:n:ioff1) = 1.0d0 / t2(i1:n:ioff1) c c compute pivots. First = lower part, second = upper part. c CVD$ NOSYNC tt(k0:k) = t1(i0:n:ioff1) * t2(i1:i2:ioff1) CVD$ NOSYNC t2(i0:n:ioff1) = t2(i0:n:ioff1) - tt(k0:k)*t3(i1:i2:ioff1) CVD$ NOSYNC t1(i0:n:ioff1) = -t1(i1:i2:ioff1)*tt(k0:k) c upper transformation k1 = n+is+k0 k2 = n+is+k CVD$ NOSYNC tt(k1:k2) = t3(1:i2:ioff1) * t2(i1:n:ioff1) CVD$ NOSYNC t2(1:i2:ioff1)=t2(1:i2:ioff1)-tt(k1:k2)*t1(i1:n:ioff1) CVD$ NOSYNC t3(1:i2:ioff1) = -t3(i1:n:ioff1)*tt(k1:k2) 21 continue c------------------------------------------------------------- c solve residual tridiagonal system ----- c 1) forward sweep c------------------------------------------------------------- k = 1 22 t2(k) = 1.0d0 / t2(k) k = k+ioff1 dpiv = t1(k)*t2(k-ioff1) t2(k) = (t2(k) - dpiv*t3(k-ioff1)) t1(k) = dpiv if (k+ioff1 .le. n) goto 22 t2(k) = 1.0d0 / t2(k) return end c---------------------------------------------------------------------- subroutine tridcs2 (n, is, t1, t2, t3, tt, z) c-----------------------------------------------------------------------* c Cyclic reduction for solving the tridiagonal system T x = z, where T * c is a nonsymmetric and tridiagonal matrix. This routine subroutine does* c the solution part and assumes that the arrays t1, t2, t3, tt have been* c processed by tridcf2. To solve a system, first call * c tridcf2 then follow it by a call to tridcs2 for each system to solve. * c warning: the matrices t1, t2, t3, tt should not be modified between * c the successive calls. * c-----------------------------------------------------------------------* c argument list: * c input : * c n = integer equal to the dimension of the problem. * c is = number of cyclic reduction steps to be taken. * c t1 = real*8 array of size n, containing the subdiagonal of T * c t2 = real*8 array of size n containing the diagonal matrix * c t3 = real*8 array of size n containing the super-diagonal of T * c The nonzero elements of T are stored in t1, t2, t3 in such a way* c that t1(i), t2(i), t3(i) are the nonzero elements of the i-th * c row of T. t1(1) and t3(n) are never used. * c z = real*8 array of size n containing the right hand side. * c tt = real*8 array of size at least 2*n + log2(n), used to store the* c pivot information during the elimination process. * c output: * c z is replaced by the solution to the system * c-----------------------------------------------------------------------* real*8 t1(n), t2(n), t3(n), z(n), tt(n), dpiv c-----------------------------------------------------------------------* k =0 ioff1 = 1 do 21 j=1, is ioff0 = ioff1 ioff1 = ioff1 + ioff1 i0 = ioff1+1 i1 = i0-ioff0 i2 = n - ioff0 k0 = k +1 k = k + ((n-1)/ioff1 +1) k1 = n+is+k0 k2 = n+is+k c CVD$ NOSYNC z(i0:n:ioff1) = z(i0:n:ioff1)-tt(k0:k)*z(i1:i2:ioff1) c CVD$ NOSYNC z(1:i2:ioff1)=z(1:i2:ioff1)-tt(k1:k2)*z(i1:i2:ioff1) 21 continue c------------------------------------------------------------- c solve residual tridiagonal system ----- c 1) forward sweep c------------------------------------------------------------- k = 1 22 k = k+ioff1 z(k) = z(k) - t1(k)*z(k-ioff1) if (k+ioff1 .le. n) goto 22 z(k) = z(k) * t2(k) c 2) backward sweep 23 k = k -ioff1 z(k) = (z(k) - t3(k)*z(k+ioff1))*t2(k) if (k .gt. ioff1) goto 23 c------------------------------------------------------------- c---- finally solve " even equations " ----------------------- c------------------------------------------------------------- do 24 j=1, is ioff0 = ioff1/2 i0 = ioff0+1 i2 = n - ioff0 i3 = ioff1 + 1 CVD$ NOSYNC z(i0:n:ioff1)=(z(i0:n:ioff1)-t1(i0:n:ioff1)*z(1:n:ioff1) - * t3(i0:n:ioff1)*z(i3:n:ioff1))*t2(i0:n:ioff1) ioff1 = ioff0 24 continue return end c---------------------------------------------------------------------- subroutine tridfs2 (n, is, t1, t2, t3, tt, z) c-----------------------------------------------------------------------* c Cyclic reduction for solving the tridiagonal system T x = z, where T * c is a nonsymmetric diagonally dominant tridigonal matrix. * c This is the standard cyclic reduction method for solving one * c tridiagonal system once. If the system must be solved many times * c a better alternative may be to use the subroutine tridf followed by * c trids or tridf2 followed by trids2 * c-----------------------------------------------------------------------* c list of parameters: * c input : * c n = integer equal to the dimension of the problem. * c is = number of cyclic reduction steps to be taken. If the value of * c is is negative of if 2**is+1 exceeds n then the code chooses * c a default value. * c t1 = real*8 array of size n, containing the subdiagonal of T * c starting at t1(2). * c t2 = real*8 array of size n containing the diagonal matrix * c t3 = real*8 array of size n containing the super-diagonal of T * c z = real*8 array of size n containing the right hand side. * c tt = real*8 work array of size n. * c output: * c t1, t2 are destroyed. * c z contains the solution. * c WARNING THIS CODE DOES NOT INTERCHANGE rows or colums in case of small* c pivots. If the matrix is not positive definite problems may arise. * c-----------------------------------------------------------------------* real*8 t1(n), t2(n), t3(n), z(n), tt(n), dpiv c------------------------------------------------------------- c chose alternate value for is if the one given is not valid. k = log2c(n) if (is .ge. 0 .and. is .le. k) goto 10 c--------- this choice is based on vectorization only -------- c (stop reducing when vector length is less than 16) -------- is = max0(0,k-4) c------------------------------------------------------------- 10 k =0 ioff1 = 1 do 21 j=1, is ioff0 = ioff1 ioff1 = ioff1 + ioff1 i0 = ioff1+1 i1 = i0-ioff0 i2 = n - ioff0 k0 = k +1 k = k + n/ioff1 +1 c keep diagonal in inverted form CVD$ NOSYNC t2(i1:n:ioff1) = 1.0d0 / t2(i1:n:ioff1) c c compute pivots. First = lower part, second = upper part. c CVD$ NOSYNC tt(k0:k) = t1(i0:n:ioff1) * t2(i1:i2:ioff1) CVD$ NOSYNC z(i0:n:ioff1) = z(i0:n:ioff1)-tt(k0:k)*z(i1:i2:ioff1) CVD$ NOSYNC t2(i0:n:ioff1) = t2(i0:n:ioff1) - tt(k0:k)*t3(i1:i2:ioff1) CVD$ NOSYNC t1(i0:n:ioff1) = -t1(i1:i2:ioff1)*tt(k0:k) c upper transformation k1 = n+k0 k2 = n+k CVD$ NOSYNC tt(k1:k2) = t3(1:i2:ioff1) * t2(i1:n:ioff1) CVD$ NOSYNC z(1:i2:ioff1)=z(1:i2:ioff1)-tt(k1:k2)*z(i1:i2:ioff1) CVD$ NOSYNC t2(1:i2:ioff1)=t2(1:i2:ioff1)-tt(k1:k2)*t1(i1:n:ioff1) CVD$ NOSYNC t3(1:i2:ioff1) = -t3(i1:n:ioff1)*tt(k1:k2) 21 continue c------------------------------------------------------------- c solve residual tridiagonal system ----- c 1) forward sweep c------------------------------------------------------------- k = 1 22 t2(k) = 1.0d0 / t2(k) k = k+ioff1 dpiv = t1(k)*t2(k-ioff1) z(k) = z(k) - dpiv*z(k-ioff1) t2(k) = t2(k) - dpiv*t3(k-ioff1) if (k+ioff1 .le. n) goto 22 z(k) = z(k) / t2(k) c 2) backward sweep 23 k = k -ioff1 z(k) = (z(k) - t3(k)*z(k+ioff1))*t2(k) if (k .gt. ioff1) goto 23 c------------------------------------------------------------- c---- finally solve " even equations " ----------------------- c------------------------------------------------------------- do 24 j=1, is ioff0 = ioff1/2 i0 = ioff0+1 i2 = n - ioff0 i3 = ioff1 + 1 CVD$ NOSYNC z(i0:n:ioff1)=(z(i0:n:ioff1)-t1(i0:n:ioff1)*z(1:n:ioff1) - * t3(i0:n:ioff1)*z(i3:n:ioff1))*t2(i0:n:ioff1) ioff1 = ioff0 24 continue return end .