Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download

GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it

563641 views
Tweet
Share
Share
1
#include"typedef.h"

2
#include"matrix.h"

3
#include"symm.h"

4
/**************************************************************************\

5
@---------------------------------------------------------------------------

6
@---------------------------------------------------------------------------

7
@ FILE: short_reduce.c

8
@---------------------------------------------------------------------------

9
@---------------------------------------------------------------------------

10
@

11
\**************************************************************************/

12


13


14


15
/**************************************************************************\

16
@---------------------------------------------------------------------------

17
@ matrix_TYP *short_reduce(A, SV, Trf)

18
@ matrix_TYP *A, *SV, *Trf;

19
@

20
@ short_reduce make a reduction of the matrix A using the shortvectors

21
@ given in SV.

22
@ If an entry in SV is 1 or -1 the vector is used to make A better

23
@ afterwards the vectors in SV are transformed and the same is tried

24
@ again.

25
@ A and SV are not changed in this function.

26
@ the result is the reduced matrix and the transformation is

27
@ applied to the matrix Trf.

28
@---------------------------------------------------------------------------

29
@

30
\**************************************************************************/

31
matrix_TYP *short_reduce(A, SV, Trf)

32
matrix_TYP *A, *SV, *Trf;

33
{

34


35
   int step, i,j,k,l, dim;

36
   int min, min1, max, anz;

37
   int **B, **Titr ,**T, **S ;

38
   matrix_TYP *Aneu;

39
   int abbruch, lastchange, merk, *mp;

40
   int *v;

41


42
   dim = A->cols;

43
   min = SV->array.SZ[0][dim];

44
   anz = SV->rows;

45
   if( (v = (int *)malloc(dim *sizeof(int ))) == NULL){

46
     printf("malloc of 'v' in short_reduce failed\n");

47
     exit(2);

48
   }

49
   Aneu = copy_mat(A);

50
   B = Aneu->array.SZ;

51
   if(Trf != NULL)

52
     T = Trf->array.SZ;

53
   else

54
     T = NULL;

55
   S = SV->array.SZ;

56
   if( (Titr = (int **)malloc(dim *sizeof(int *))) == NULL){

57
     printf("malloc of 'Titr' in short_reduce failed\n");

58
     exit(2);

59
   }

60
   for(i=0;i<dim;i++)

61
   {

62
     if( (Titr[i] = (int *)malloc(dim *sizeof(int))) == NULL)

63
     {

64
       printf("malloc of 'Titr[%d]' in short_reduce failed\n", i);

65
       exit(2);

66
     }

67
     for(j=0;j<dim;j++)

68
       Titr[i][j] = 0;

69
     Titr[i][i] = 1;

70
   }

71
   min1 = B[0][0];

72
   max = B[0][0];

73
   for(i=1; i<dim;i++)

74
   {

75
     if(B[i][i] < min1)

76
        min1 = B[i][i];

77
     if(B[i][i] > max)

78
        max = B[i][i];

79
   }

80
   if(max == min)

81
   { for(i=0;i<dim;i++)

82
       free(Titr[i]);

83
       free(Titr);

84
       return(Aneu);

85
   }

86
   if(min1 == min)

87
   {

88
     abbruch = FALSE;

89
     for(step=0;step<dim && abbruch == FALSE;step++)

90
     {

91
       if(B[step][step] != min)

92
       {

93
          for(i=step+1;i<dim && B[i][i] != min ;i++);

94
          if(i == dim)

95
            abbruch = TRUE;

96
          else

97
          {

98
             if(T != NULL)

99
             {

100
               mp = T[step];

101
               T[step] = T[i];

102
               T[i] = mp;

103
             }

104
             mp = Titr[step];

105
             Titr[step] = Titr[i];

106
             Titr[i] = mp;

107
             mp = B[step];

108
             B[step] = B[i];

109
             B[i] = mp;

110
             for(j=0;j<dim;j++)

111
             {

112
                merk = B[j][step];

113
                B[j][step] = B[j][i];

114
                B[j][i] = merk;

115
             }

116
          }

117
       }

118
     }

119
   }

120
   for(step = 0;step<dim && B[step][step] == min; step++);

121
   lastchange = anz;

122
   abbruch = FALSE;

123
   while(step < dim && abbruch == FALSE)

124
   {

125
      for(i=0;i<anz && step < dim && i != lastchange ;i++)

126
      {

127
        /*----------------------------------------------------*\

128
        | Calculate S[i] * Titr^{tr}

129
        \*----------------------------------------------------*/

130
         for(k=step;k<dim;k++)

131
         {

132
           v[k] = 0;

133
           for(l=0;l<dim;l++)

134
             v[k] += S[i][l] * Titr[k][l];

135
         }

136
         for(k=step;k<dim && v[k] != 1 && v[k] != -1; k++);

137
         if(k<dim)

138
         {

139
           lastchange = i;

140
           for(j = 0;j<step;j++)

141
           {

142
             v[j] = 0;

143
             for(l=0;l<dim;l++)

144
               v[j] += S[i][l] * Titr[j][l];

145
           }

146
           if(v[k] == -1)

147
           {

148
             for(j=0;j<dim;j++)

149
               v[j] = -v[j];

150
           }

151
           if(k != step)

152
           {

153
              if(T != NULL)

154
              {

155
                mp = T[step];

156
                T[step] = T[k];

157
                T[k] = mp;

158
              }

159
              mp = Titr[step];

160
              Titr[step] = Titr[k];

161
              Titr[k] = mp;

162
              mp = B[step];

163
              B[step] = B[k];

164
              B[k] = mp;

165
              for(l=0;l<dim;l++)

166
              { merk = B[l][step]; B[l][step] = B[l][k]; B[l][k] = merk;}

167
              merk = v[step]; v[step] = v[k]; v[k] = merk;

168
           }

169
           for(j=0;j<step;j++)

170
           {

171
             if(v[j] != 0)

172
             {

173
                for(l=0;l<dim;l++)

174
                {

175
                  if(T != NULL)

176
                    T[step][l] += T[j][l] * v[j];

177
                  Titr[j][l] -= Titr[step][l] * v[j];

178
                  B[step][l] += B[j][l] * v[j];

179
                }

180
             }

181
           }

182
           for(j=step+1;j<dim;j++)

183
           {

184
             if(v[j] != 0)

185
             {

186
                for(l=0;l<dim;l++)

187
                {

188
                  if(T != NULL)

189
                    T[step][l] += T[j][l] * v[j];

190
                  Titr[j][l] -= Titr[step][l] * v[j];

191
/*

192
                  Titr[l][step] -= Titr[l][j] * v[j];

193
*/

194
                  B[step][l] += B[j][l] * v[j];

195
                }

196
             }

197
           }

198
           for(j=0;j<step;j++)

199
           {

200
             if(v[j] != 0)

201
             {

202
                for(l=0;l<dim;l++)

203
                  B[l][step] += B[l][j] * v[j];

204
             }

205
           }

206
           for(j=step+1;j<dim;j++)

207
           {

208
             if(v[j] != 0)

209
             {

210
                for(l=0;l<dim;l++)

211
                  B[l][step] += B[l][j] * v[j];

212
             }

213
           }

214
         step++;

215
         }

216
      }

217
      if(i == lastchange)

218
         abbruch = TRUE;

219
   }

220
   for(i=0;i<dim;i++)

221
     free(Titr[i]);

222
   free(Titr);

223
   free(v);

224
   return(Aneu);

225
}

226


227


228


229
/**************************************************************************\

230
@---------------------------------------------------------------------------

231
@ matrix_TYP *pr_short_red(A, Trf)

232
@ matrix_TYP *A, *Trf;

233
@

234
@ The same as short_reduce but before and after using this function

235
@ a pair_redduction is used.

236
@ The shortest vectors are calculated by the function itsself.

237
@---------------------------------------------------------------------------

238
@

239
\**************************************************************************/

240
matrix_TYP *pr_short_red(A, Trf)

241
matrix_TYP *A, *Trf;

242
{

243
   matrix_TYP *Aneu, *Aneu1, *Aneu2, *SV;

244
   int i,j,k, min, max, min1, dim;

245
   int anz, len;

246
   int is_even;

247


248
   dim = A->cols;

249
   Aneu = copy_mat(A);

250
   is_even = TRUE;

251
   for(i=0;i<dim && is_even == TRUE; i++)

252
   {

253
      if( (A->array.SZ[i][i]%2) != 0)

254
        is_even = FALSE;

255
   }

256
   pr_red(Aneu->array.SZ, Trf->array.SZ, dim);

257
   min1 = Aneu->array.SZ[0][0];

258
   max = Aneu->array.SZ[0][0];

259
   for(i=1;i<dim;i++)

260
   {

261
     if(Aneu->array.SZ[i][i] < min1)

262
       min1 = A->array.SZ[i][i];  

263
     if(Aneu->array.SZ[i][i] > max)

264
       max = A->array.SZ[i][i];  

265
   }

266
   if(is_even == TRUE)

267
     len = min1 - 2;

268
   else

269
     len = min1 -1;

270


271
   /* changed 17/1/97 from:

272
   short_vectors(Aneu, len, 0, 1, 1, &anz);

273
   to: */

274
   SV = short_vectors(Aneu, len, 0, 1, 1, &anz);

275
   free_mat(SV);

276


277
   if(anz == 0 && max == min1)

278
      return(Aneu);

279
   SV = shortest(Aneu, &min);

280
   Aneu1 = short_reduce(Aneu, SV, Trf);

281
   free_mat(SV);

282
   free_mat(Aneu);

283
   if(Aneu1->array.SZ[dim-1][dim-1] == min)

284
      return(Aneu1);

285
   pr_red(Aneu1->array.SZ, Trf->array.SZ, dim);

286
   return(Aneu1);

287
}

288


289