| 1 |
! Copyright © 2022-2026 Dynare Team |
| 2 |
! |
| 3 |
! This file is part of Dynare. |
| 4 |
! |
| 5 |
! Dynare is free software: you can redistribute it and/or modify |
| 6 |
! it under the terms of the GNU General Public License as published by |
| 7 |
! the Free Software Foundation, either version 3 of the License, or |
| 8 |
! (at your option) any later version. |
| 9 |
! |
| 10 |
! Dynare is distributed in the hope that it will be useful, |
| 11 |
! but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 12 |
! MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 13 |
! GNU General Public License for more details. |
| 14 |
! |
| 15 |
! You should have received a copy of the GNU General Public License |
| 16 |
! along with Dynare. If not, see <https://www.gnu.org/licenses/>. |
| 17 |
|
| 18 |
! Implements the cyclic reduction algorithm described in |
| 19 |
! D.A. Bini, G. Latouche, B. Meini (2002), "Solving matrix polynomial equations arising in queueing problems", Linear Algebra and its Applications 340, pp. 222-244 |
| 20 |
! D.A. Bini, B. Meini (1996), "On the solution of a nonlinear matrix equation arising in queueing problems", SIAM J. Matrix Anal. Appl. 17, pp. 906-926. |
| 21 |
module c_reduction |
| 22 |
use lapack |
| 23 |
use blas |
| 24 |
use matlab_mex |
| 25 |
use ieee_arithmetic |
| 26 |
implicit none (type, external) |
| 27 |
|
| 28 |
contains |
| 29 |
|
| 30 |
! Cycle reduction algorithm |
| 31 |
subroutine cycle_reduction(A0, A1, A2, X, cvg_tol, check, max_it, info) |
| 32 |
real(real64), dimension(:,:), intent(in) :: A0, A1, A2 |
| 33 |
real(real64), dimension(:,:), intent(inout) :: X |
| 34 |
real(real64), intent(in) :: cvg_tol |
| 35 |
logical, intent(in) :: check |
| 36 |
integer, intent(in) :: max_it |
| 37 |
real(c_double), dimension(2), intent(inout) :: info |
| 38 |
|
| 39 |
real(real64), dimension(:,:), allocatable :: A02, & |
| 40 |
Q0, Q2, Ahat, invA1_A02, A1i, A0_tmp, A1_tmp |
| 41 |
integer :: it, n, dn |
| 42 |
integer(blint) :: info_inv |
| 43 |
integer(blint), dimension(:), allocatable :: ipiv |
| 44 |
real(real64) :: residual, crit |
| 45 |
character(kind=c_char, len=10) :: cvg_tol_str, residual_str |
| 46 |
|
| 47 |
n = size(A0,1) |
| 48 |
dn = 2*n |
| 49 |
allocate(A02(n,dn), ipiv(n), invA1_A02(n,dn), Q0(n,dn), Q2(n,dn)) |
| 50 |
A02(:,1:n) = A0 |
| 51 |
A02(:,n+1:dn) = A2 |
| 52 |
Ahat = A1 |
| 53 |
A1i = A1 |
| 54 |
it = 0 |
| 55 |
loop: do |
| 56 |
! Computing [A0;A2]*(A1\[A0 A2]) |
| 57 |
A1_tmp = A1i |
| 58 |
invA1_A02 = A02 |
| 59 |
call left_divide(A1_tmp, invA1_A02, ipiv, info_inv) |
| 60 |
call matmul_add("N", "N", 1._real64, A02(:,1:n), invA1_A02, 0._real64, Q0) |
| 61 |
call matmul_add("N", "N", 1._real64, A02(:,n+1:dn), invA1_A02, 0._real64, Q2) |
| 62 |
! Updating A02, A1 and Ahat |
| 63 |
A1i = A1i - Q0(:,n+1:dn) - Q2(:,1:n) |
| 64 |
A02(:,1:n) = -Q0(:,1:n) |
| 65 |
A02(:,n+1:dn) = -Q2(:,n+1:dn) |
| 66 |
Ahat = Ahat-Q2(:,1:n) |
| 67 |
crit = norm(A02(:,1:n),"1") |
| 68 |
! Checking for stopping conditions |
| 69 |
if (crit < cvg_tol) then |
| 70 |
if (norm(A02(:,n+1:dn), "1") < cvg_tol) exit loop |
| 71 |
elseif (it == max_it) then |
| 72 |
info(1) = 401._c_double |
| 73 |
info(2) = real(log(norm(A1i,"1")), c_double) |
| 74 |
exit loop |
| 75 |
elseif (ieee_is_nan(crit) .or. (info_inv /= 0_blint)) then |
| 76 |
info(1) = 402._c_double |
| 77 |
info(2) = real(log(norm(A1i,"1")), c_double) |
| 78 |
exit loop |
| 79 |
end if |
| 80 |
it = it + 1 |
| 81 |
end do loop |
| 82 |
|
| 83 |
! Computing X = -Ahat\A0 |
| 84 |
X = -A0 |
| 85 |
call left_divide(Ahat, X, ipiv, info_inv) |
| 86 |
|
| 87 |
! Checking residuals if necessary |
| 88 |
if (check) then |
| 89 |
! A1_tmp <- A2*X + A1 |
| 90 |
A1_tmp = A1 |
| 91 |
call matmul_add("N", "N", 1._real64, A2, X, 1._real64, A1_tmp) |
| 92 |
! A0_tmp <- A1_tmp*X + A0 |
| 93 |
A0_tmp = A0 |
| 94 |
call matmul_add("N", "N", 1._real64, A1_tmp, X, 1._real64, A0_tmp) |
| 95 |
residual = norm(A0_tmp, "1") |
| 96 |
if (residual>cvg_tol) then |
| 97 |
info(1) = 403._c_double |
| 98 |
info(2) = log(residual) |
| 99 |
write (cvg_tol_str,"(es8.2)") cvg_tol |
| 100 |
write (residual_str,"(es8.2)") residual |
| 101 |
call mexPrintf("The norm of the residual is "& |
| 102 |
&// trim(residual_str) // & |
| 103 |
&", whereas the tolerance criterion is " & |
| 104 |
// trim(cvg_tol_str) // "." ) |
| 105 |
end if |
| 106 |
end if |
| 107 |
end subroutine cycle_reduction |
| 108 |
|
| 109 |
end module c_reduction |
| 110 |
|
| 111 |
subroutine mexFunction(nlhs, plhs, nrhs, prhs) bind(c, name='mexFunction') |
| 112 |
use c_reduction |
| 113 |
implicit none (type, external) |
| 114 |
|
| 115 |
type(c_ptr), dimension(*), intent(in) :: prhs |
| 116 |
type(c_ptr), dimension(*), intent(out) :: plhs |
| 117 |
integer(c_int), intent(in), value :: nlhs, nrhs |
| 118 |
|
| 119 |
integer :: i, n, max_it |
| 120 |
character(kind=c_char, len=2) :: num2str |
| 121 |
real(real64) :: cvg_tol |
| 122 |
real(real64), dimension(:,:), pointer, contiguous :: A0, A1, A2, X |
| 123 |
real(real64), dimension(2) :: info |
| 124 |
logical :: check |
| 125 |
|
| 126 |
! 0. Checking the consistency and validity of input arguments |
| 127 |
if (nrhs < 4) call mexErrMsgTxt("Must have at least 4 inputs") |
| 128 |
if (nrhs > 5) call mexErrMsgTxt("Too many input arguments") |
| 129 |
if (nlhs > 2) call mexErrMsgTxt("Too many output arguments") |
| 130 |
|
| 131 |
do i=1,3 |
| 132 |
if (.not. (c_associated(prhs(i)) .and. mxIsDouble(prhs(i)) .and. & |
| 133 |
(.not. mxIsComplex(prhs(i))) .and. (.not. mxIsSparse(prhs(i))))) then |
| 134 |
write (num2str,"(i2)") i |
| 135 |
call mexErrMsgTxt("Argument" // trim(num2str) // " should be a real dense matrix") |
| 136 |
end if |
| 137 |
end do |
| 138 |
if (.not. (c_associated(prhs(4)) .and. mxIsScalar(prhs(4)) .and. & |
| 139 |
mxIsNumeric(prhs(4)))) & |
| 140 |
call mexErrMsgTxt("Argument 4 should be a numeric scalar") |
| 141 |
|
| 142 |
check = .false. |
| 143 |
if (nrhs == 5) then |
| 144 |
if (.not. (c_associated(prhs(5)))) then |
| 145 |
call mexErrMsgTxt("Argument 5 should be a Matlab object") |
| 146 |
else |
| 147 |
if (.not. mxIsEmpty(prhs(5))) check = .true. |
| 148 |
end if |
| 149 |
end if |
| 150 |
|
| 151 |
n = int(mxGetM(prhs(1))) ! Order of the considered matrices |
| 152 |
if (n /= mxGetN(prhs(1)) & ! Number of columns of A0 |
| 153 |
.or. n /= mxGetM(prhs(2)) & ! Number of lines of A1 |
| 154 |
.or. n /= mxGetN(prhs(2)) & ! Number of columns of A1 |
| 155 |
.or. n /= mxGetM(prhs(3)) & ! Number of lines of A2 |
| 156 |
.or. n /= mxGetN(prhs(3))) & ! Number of columns of A2 |
| 157 |
call mexErrMsgTxt("Input dimension mismatch") |
| 158 |
|
| 159 |
! 1. Storing the relevant information in Fortran format |
| 160 |
A0(1:n,1:n) => mxGetDoubles(prhs(1)) |
| 161 |
A1(1:n,1:n) => mxGetDoubles(prhs(2)) |
| 162 |
A2(1:n,1:n) => mxGetDoubles(prhs(3)) |
| 163 |
cvg_tol = mxGetScalar(prhs(4)) |
| 164 |
max_it = int(mxGetScalar(prhs(5))) |
| 165 |
info = [0._c_double,0._c_double] |
| 166 |
|
| 167 |
plhs(1) = mxCreateDoubleMatrix(int(n, mwSize), int(n, mwSize), mxREAL) |
| 168 |
X(1:n,1:n) => mxGetDoubles(plhs(1)) |
| 169 |
|
| 170 |
! 2. Calling the Cycle Reduction algorithm |
| 171 |
call cycle_reduction(A0, A1, A2, X, cvg_tol, check, max_it, info) |
| 172 |
|
| 173 |
! 3. Editing the information output if necessary |
| 174 |
if (nlhs == 2) then |
| 175 |
if (info(1) == 0.) then |
| 176 |
plhs(2) = mxCreateDoubleScalar(0._c_double) |
| 177 |
else |
| 178 |
plhs(2) = mxCreateDoubleMatrix(1_mwSize, 2_mwSize, mxREAL) |
| 179 |
mxGetDoubles(plhs(2)) = info |
| 180 |
end if |
| 181 |
end if |
| 182 |
|
| 183 |
end subroutine mexFunction |