Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is to exceed 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - basemath - RgV.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.12.1 lcov report (development 25406-bf255ab81b) Lines: 503 557 90.3 %
Date: 2020-06-04 05:59:24 Functions: 91 98 92.9 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2000  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : #include "pari.h"
      15             : #include "paripriv.h"
      16             : 
      17             : int
      18      507941 : RgM_is_ZM(GEN x)
      19             : {
      20      507941 :   long i, j, h, l = lg(x);
      21      507941 :   if (l == 1) return 1;
      22      507703 :   h = lgcols(x);
      23      507703 :   if (h == 1) return 1;
      24     2282767 :   for (j = l-1; j > 0; j--)
      25    12113655 :     for (i = h-1; i > 0; i--)
      26    10338591 :       if (typ(gcoeff(x,i,j)) != t_INT) return 0;
      27      471003 :   return 1;
      28             : }
      29             : 
      30             : int
      31         203 : RgM_is_QM(GEN x)
      32             : {
      33         203 :   long i, j, h, l = lg(x);
      34         203 :   if (l == 1) return 1;
      35         189 :   h = lgcols(x);
      36         189 :   if (h == 1) return 1;
      37        1218 :   for (j = l-1; j > 0; j--)
      38       15057 :     for (i = h-1; i > 0; i--)
      39       14028 :       if (!is_rational_t(typ(gcoeff(x,i,j)))) return 0;
      40         175 :   return 1;
      41             : }
      42             : 
      43             : int
      44          35 : RgV_is_ZMV(GEN V)
      45             : {
      46          35 :   long i, l = lg(V);
      47         357 :   for (i=1; i<l; i++)
      48         322 :     if (typ(gel(V,i))!=t_MAT || !RgM_is_ZM(gel(V,i)))
      49           0 :       return 0;
      50          35 :   return 1;
      51             : }
      52             : 
      53             : /********************************************************************/
      54             : /**                                                                **/
      55             : /**                   GENERIC LINEAR ALGEBRA                       **/
      56             : /**                                                                **/
      57             : /********************************************************************/
      58             : /*           GENERIC  MULTIPLICATION involving zc/zm                */
      59             : 
      60             : /* x[i,] * y */
      61             : static GEN
      62     4698780 : RgMrow_zc_mul_i(GEN x, GEN y, long c, long i)
      63             : {
      64     4698780 :   pari_sp av = avma;
      65     4698780 :   GEN s = NULL;
      66             :   long j;
      67   682133819 :   for (j=1; j<c; j++)
      68             :   {
      69   677435039 :     long t = y[j];
      70   677435039 :     if (!t) continue;
      71    17996351 :     if (!s) { s = gmulgs(gcoeff(x,i,j),t); continue; }
      72    13361436 :     switch(t)
      73             :     {
      74    10440279 :       case  1: s = gadd(s, gcoeff(x,i,j)); break;
      75      233235 :       case -1: s = gsub(s, gcoeff(x,i,j)); break;
      76     2687922 :       default: s = gadd(s, gmulgs(gcoeff(x,i,j), t)); break;
      77             :     }
      78             :   }
      79     4698780 :   if (!s) { set_avma(av); return gen_0; }
      80     4634915 :   return gerepileupto(av, s);
      81             : }
      82             : GEN
      83       69937 : RgMrow_zc_mul(GEN x, GEN y, long i) { return RgMrow_zc_mul_i(x,y,lg(y),i); }
      84             : /* x non-empty t_MAT, y a compatible zc (dimension > 0). */
      85             : static GEN
      86      124696 : RgM_zc_mul_i(GEN x, GEN y, long c, long l)
      87             : {
      88      124696 :   GEN z = cgetg(l,t_COL);
      89             :   long i;
      90     4753539 :   for (i = 1; i < l; i++) gel(z,i) = RgMrow_zc_mul_i(x,y,c,i);
      91      124696 :   return z;
      92             : }
      93             : GEN
      94       71736 : RgM_zc_mul(GEN x, GEN y) { return RgM_zc_mul_i(x,y, lg(x), lgcols(x)); }
      95             : /* x t_MAT, y a compatible zm (dimension > 0). */
      96             : GEN
      97       15065 : RgM_zm_mul(GEN x, GEN y)
      98             : {
      99       15065 :   long j, c, l = lg(x), ly = lg(y);
     100       15065 :   GEN z = cgetg(ly, t_MAT);
     101       15065 :   if (l == 1) return z;
     102       15065 :   c = lgcols(x);
     103       68025 :   for (j = 1; j < ly; j++) gel(z,j) = RgM_zc_mul_i(x, gel(y,j), l,c);
     104       15065 :   return z;
     105             : }
     106             : 
     107             : static GEN
     108       38068 : RgV_zc_mul_i(GEN x, GEN y, long l)
     109             : {
     110             :   long i;
     111       38068 :   GEN z = gen_0;
     112       38068 :   pari_sp av = avma;
     113     4295629 :   for (i = 1; i < l; i++) z = gadd(z, gmulgs(gel(x,i), y[i]));
     114       38068 :   return gerepileupto(av, z);
     115             : }
     116             : GEN
     117        6804 : RgV_zc_mul(GEN x, GEN y) { return RgV_zc_mul_i(x, y, lg(x)); }
     118             : 
     119             : GEN
     120        7564 : RgV_zm_mul(GEN x, GEN y)
     121             : {
     122        7564 :   long j, l = lg(x), ly = lg(y);
     123        7564 :   GEN z = cgetg(ly, t_VEC);
     124       38828 :   for (j = 1; j < ly; j++) gel(z,j) = RgV_zc_mul_i(x, gel(y,j), l);
     125        7564 :   return z;
     126             : }
     127             : 
     128             : /* scalar product x.x */
     129             : GEN
     130        5277 : RgV_dotsquare(GEN x)
     131             : {
     132        5277 :   long i, lx = lg(x);
     133        5277 :   pari_sp av = avma;
     134             :   GEN z;
     135        5277 :   if (lx == 1) return gen_0;
     136        5277 :   z = gsqr(gel(x,1));
     137      688841 :   for (i=2; i<lx; i++)
     138             :   {
     139      683564 :     z = gadd(z, gsqr(gel(x,i)));
     140      683564 :     if (gc_needed(av,3))
     141             :     {
     142           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgV_dotsquare, i = %ld",i);
     143           0 :       z = gerepileupto(av, z);
     144             :     }
     145             :   }
     146        5277 :   return gerepileupto(av,z);
     147             : }
     148             : 
     149             : /* scalar product x.y, lx = lg(x) = lg(y) */
     150             : static GEN
     151     2124989 : RgV_dotproduct_i(GEN x, GEN y, long lx)
     152             : {
     153     2124989 :   pari_sp av = avma;
     154             :   long i;
     155             :   GEN z;
     156     2124989 :   if (lx == 1) return gen_0;
     157     2124989 :   z = gmul(gel(x,1),gel(y,1));
     158    48486407 :   for (i=2; i<lx; i++)
     159             :   {
     160    46361425 :     z = gadd(z, gmul(gel(x,i), gel(y,i)));
     161    46361435 :     if (gc_needed(av,3))
     162             :     {
     163           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgV_dotproduct, i = %ld",i);
     164           0 :       z = gerepileupto(av, z);
     165             :     }
     166             :   }
     167     2124982 :   return gerepileupto(av,z);
     168             : }
     169             : GEN
     170      159444 : RgV_dotproduct(GEN x,GEN y)
     171             : {
     172      159444 :   if (x == y) return RgV_dotsquare(x);
     173      159444 :   return RgV_dotproduct_i(x, y, lg(x));
     174             : }
     175             : /* v[1] + ... + v[lg(v)-1] */
     176             : GEN
     177      589831 : RgV_sum(GEN v)
     178             : {
     179             :   GEN p;
     180      589831 :   long i, l = lg(v);
     181      589831 :   if (l == 1) return gen_0;
     182     1532265 :   p = gel(v,1); for (i=2; i<l; i++) p = gadd(p, gel(v,i));
     183      589831 :   return p;
     184             : }
     185             : /* v[1] + ... + v[n]. Assume lg(v) > n. */
     186             : GEN
     187        1032 : RgV_sumpart(GEN v, long n)
     188             : {
     189             :   GEN p;
     190             :   long i;
     191        1032 :   if (!n) return gen_0;
     192        2512 :   p = gel(v,1); for (i=2; i<=n; i++) p = gadd(p, gel(v,i));
     193        1032 :   return p;
     194             : }
     195             : /* v[m] + ... + v[n]. Assume lg(v) > n, m > 0. */
     196             : GEN
     197           0 : RgV_sumpart2(GEN v, long m, long n)
     198             : {
     199             :   GEN p;
     200             :   long i;
     201           0 :   if (n < m) return gen_0;
     202           0 :   p = gel(v,m); for (i=m+1; i<=n; i++) p = gadd(p, gel(v,i));
     203           0 :   return p;
     204             : }
     205             : GEN
     206         432 : RgM_sumcol(GEN A)
     207             : {
     208         432 :   long i,j,m,l = lg(A);
     209             :   GEN v;
     210             : 
     211         432 :   if (l == 1) return cgetg(1,t_MAT);
     212         432 :   if (l == 2) return gcopy(gel(A,1));
     213         208 :   m = lgcols(A);
     214         208 :   v = cgetg(m, t_COL);
     215         680 :   for (i = 1; i < m; i++)
     216             :   {
     217         472 :     pari_sp av = avma;
     218         472 :     GEN s = gcoeff(A,i,1);
     219        1112 :     for (j = 2; j < l; j++) s = gadd(s, gcoeff(A,i,j));
     220         472 :     gel(v, i) = gerepileupto(av, s);
     221             :   }
     222         208 :   return v;
     223             : }
     224             : 
     225             : static GEN
     226      859894 : _gmul(void *data, GEN x, GEN y)
     227      859894 : { (void)data; return gmul(x,y); }
     228             : 
     229             : GEN
     230       61330 : RgV_prod(GEN x)
     231             : {
     232       61330 :   return gen_product(x, NULL, _gmul);
     233             : }
     234             : 
     235             : /*                    ADDITION SCALAR + MATRIX                     */
     236             : /* x square matrix, y scalar; create the square matrix x + y*Id */
     237             : GEN
     238        5760 : RgM_Rg_add(GEN x, GEN y)
     239             : {
     240        5760 :   long l = lg(x), i, j;
     241        5760 :   GEN z = cgetg(l,t_MAT);
     242             : 
     243        5760 :   if (l==1) return z;
     244        5760 :   if (l != lgcols(x)) pari_err_OP( "+", x, y);
     245        5760 :   z = cgetg(l,t_MAT);
     246       42634 :   for (i=1; i<l; i++)
     247             :   {
     248       36874 :     GEN zi = cgetg(l,t_COL), xi = gel(x,i);
     249       36874 :     gel(z,i) = zi;
     250     1893914 :     for (j=1; j<l; j++)
     251     1857040 :       gel(zi,j) = i==j? gadd(y,gel(xi,j)): gcopy(gel(xi,j));
     252             :   }
     253        5760 :   return z;
     254             : }
     255             : GEN
     256        7417 : RgM_Rg_sub(GEN x, GEN y)
     257             : {
     258        7417 :   long l = lg(x), i, j;
     259        7417 :   GEN z = cgetg(l,t_MAT);
     260             : 
     261        7417 :   if (l==1) return z;
     262        7417 :   if (l != lgcols(x)) pari_err_OP( "-", x, y);
     263        7417 :   z = cgetg(l,t_MAT);
     264       28298 :   for (i=1; i<l; i++)
     265             :   {
     266       20881 :     GEN zi = cgetg(l,t_COL), xi = gel(x,i);
     267       20881 :     gel(z,i) = zi;
     268      100346 :     for (j=1; j<l; j++)
     269       79465 :       gel(zi,j) = i==j? gsub(gel(xi,j), y): gcopy(gel(xi,j));
     270             :   }
     271        7417 :   return z;
     272             : }
     273             : GEN
     274         497 : RgM_Rg_add_shallow(GEN x, GEN y)
     275             : {
     276         497 :   long l = lg(x), i, j;
     277         497 :   GEN z = cgetg(l,t_MAT);
     278             : 
     279         497 :   if (l==1) return z;
     280         497 :   if (l != lgcols(x)) pari_err_OP( "+", x, y);
     281        1729 :   for (i=1; i<l; i++)
     282             :   {
     283        1232 :     GEN zi = cgetg(l,t_COL), xi = gel(x,i);
     284        1232 :     gel(z,i) = zi;
     285        8218 :     for (j=1; j<l; j++) gel(zi,j) = gel(xi,j);
     286        1232 :     gel(zi,i) = gadd(gel(zi,i), y);
     287             :   }
     288         497 :   return z;
     289             : }
     290             : GEN
     291      506330 : RgM_Rg_sub_shallow(GEN x, GEN y)
     292             : {
     293      506330 :   long l = lg(x), i, j;
     294      506330 :   GEN z = cgetg(l,t_MAT);
     295             : 
     296      506330 :   if (l==1) return z;
     297      506330 :   if (l != lgcols(x)) pari_err_OP( "-", x, y);
     298     2380984 :   for (i=1; i<l; i++)
     299             :   {
     300     1874654 :     GEN zi = cgetg(l,t_COL), xi = gel(x,i);
     301     1874654 :     gel(z,i) = zi;
     302    23760616 :     for (j=1; j<l; j++) gel(zi,j) = gel(xi,j);
     303     1874654 :     gel(zi,i) = gsub(gel(zi,i), y);
     304             :   }
     305      506330 :   return z;
     306             : }
     307             : 
     308             : GEN
     309     3561466 : RgC_Rg_add(GEN x, GEN y)
     310             : {
     311     3561466 :   long k, lx = lg(x);
     312     3561466 :   GEN z = cgetg(lx, t_COL);
     313     3561466 :   if (lx == 1)
     314             :   {
     315           0 :     if (isintzero(y)) return z;
     316           0 :     pari_err_TYPE2("+",x,y);
     317             :   }
     318     3561466 :   gel(z,1) = gadd(y,gel(x,1));
     319     8064003 :   for (k = 2; k < lx; k++) gel(z,k) = gcopy(gel(x,k));
     320     3561466 :   return z;
     321             : }
     322             : GEN
     323       25340 : RgC_Rg_sub(GEN x, GEN y)
     324             : {
     325       25340 :   long k, lx = lg(x);
     326       25340 :   GEN z = cgetg(lx, t_COL);
     327       25340 :   if (lx == 1)
     328             :   {
     329           0 :     if (isintzero(y)) return z;
     330           0 :     pari_err_TYPE2("-",x,y);
     331             :   }
     332       25340 :   gel(z,1) = gsub(gel(x,1), y);
     333       58079 :   for (k = 2; k < lx; k++) gel(z,k) = gcopy(gel(x,k));
     334       25340 :   return z;
     335             : }
     336             : /* a - x */
     337             : GEN
     338      109095 : Rg_RgC_sub(GEN a, GEN x)
     339             : {
     340      109095 :   long k, lx = lg(x);
     341      109095 :   GEN z = cgetg(lx,t_COL);
     342      109095 :   if (lx == 1)
     343             :   {
     344           0 :     if (isintzero(a)) return z;
     345           0 :     pari_err_TYPE2("-",a,x);
     346             :   }
     347      109095 :   gel(z,1) = gsub(a, gel(x,1));
     348      232834 :   for (k = 2; k < lx; k++) gel(z,k) = gneg(gel(x,k));
     349      109095 :   return z;
     350             : }
     351             : 
     352             : static GEN
     353    14586149 : RgC_add_i(GEN x, GEN y, long lx)
     354             : {
     355    14586149 :   GEN A = cgetg(lx, t_COL);
     356             :   long i;
     357   115892183 :   for (i=1; i<lx; i++) gel(A,i) = gadd(gel(x,i), gel(y,i));
     358    14586149 :   return A;
     359             : }
     360             : GEN
     361    11358169 : RgC_add(GEN x, GEN y) { return RgC_add_i(x, y, lg(x)); }
     362             : GEN
     363      156583 : RgV_add(GEN x, GEN y)
     364     2781305 : { pari_APPLY_type(t_VEC, gadd(gel(x,i), gel(y,i))) }
     365             : 
     366             : static GEN
     367     5536880 : RgC_sub_i(GEN x, GEN y, long lx)
     368             : {
     369             :   long i;
     370     5536880 :   GEN A = cgetg(lx, t_COL);
     371   545515846 :   for (i=1; i<lx; i++) gel(A,i) = gsub(gel(x,i), gel(y,i));
     372     5536880 :   return A;
     373             : }
     374             : GEN
     375     5456639 : RgC_sub(GEN x, GEN y) { return RgC_sub_i(x, y, lg(x)); }
     376             : GEN
     377      286461 : RgV_sub(GEN x, GEN y)
     378     2676392 : { pari_APPLY_type(t_VEC, gsub(gel(x,i), gel(y,i))) }
     379             : 
     380             : GEN
     381      675885 : RgM_add(GEN x, GEN y)
     382             : {
     383      675885 :   long lx = lg(x), l, j;
     384             :   GEN z;
     385      675885 :   if (lx == 1) return cgetg(1, t_MAT);
     386      675885 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     387     3903865 :   for (j = 1; j < lx; j++) gel(z,j) = RgC_add_i(gel(x,j), gel(y,j), l);
     388      675885 :   return z;
     389             : }
     390             : GEN
     391       31515 : RgM_sub(GEN x, GEN y)
     392             : {
     393       31515 :   long lx = lg(x), l, j;
     394             :   GEN z;
     395       31515 :   if (lx == 1) return cgetg(1, t_MAT);
     396       31515 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     397      111756 :   for (j = 1; j < lx; j++) gel(z,j) = RgC_sub_i(gel(x,j), gel(y,j), l);
     398       31515 :   return z;
     399             : }
     400             : 
     401             : static GEN
     402     3127693 : RgC_neg_i(GEN x, long lx)
     403             : {
     404             :   long i;
     405     3127693 :   GEN y = cgetg(lx, t_COL);
     406    26034953 :   for (i=1; i<lx; i++) gel(y,i) = gneg(gel(x,i));
     407     3127693 :   return y;
     408             : }
     409             : GEN
     410      159179 : RgC_neg(GEN x) { return RgC_neg_i(x, lg(x)); }
     411             : GEN
     412        2996 : RgV_neg(GEN x)
     413       54089 : { pari_APPLY_type(t_VEC, gneg(gel(x,i))) }
     414             : GEN
     415      536062 : RgM_neg(GEN x)
     416             : {
     417      536062 :   long i, hx, lx = lg(x);
     418      536062 :   GEN y = cgetg(lx, t_MAT);
     419      536062 :   if (lx == 1) return y;
     420      536055 :   hx = lgcols(x);
     421     3504569 :   for (i=1; i<lx; i++) gel(y,i) = RgC_neg_i(gel(x,i), hx);
     422      536055 :   return y;
     423             : }
     424             : 
     425             : GEN
     426     1112759 : RgV_RgC_mul(GEN x, GEN y)
     427             : {
     428     1112759 :   long lx = lg(x);
     429     1112759 :   if (lx != lg(y)) pari_err_OP("operation 'RgV_RgC_mul'", x, y);
     430     1112696 :   return RgV_dotproduct_i(x, y, lx);
     431             : }
     432             : GEN
     433        1687 : RgC_RgV_mul(GEN x, GEN y)
     434             : {
     435        1687 :   long i, ly = lg(y);
     436        1687 :   GEN z = cgetg(ly,t_MAT);
     437        5061 :   for (i=1; i<ly; i++) gel(z,i) = RgC_Rg_mul(x, gel(y,i));
     438        1687 :   return z;
     439             : }
     440             : GEN
     441           0 : RgC_RgM_mul(GEN x, GEN y)
     442             : {
     443           0 :   long i, ly = lg(y);
     444           0 :   GEN z = cgetg(ly,t_MAT);
     445           0 :   if (ly != 1 && lgcols(y) != 2) pari_err_OP("operation 'RgC_RgM_mul'",x,y);
     446           0 :   for (i=1; i<ly; i++) gel(z,i) = RgC_Rg_mul(x, gcoeff(y,1,i));
     447           0 :   return z;
     448             : }
     449             : GEN
     450           0 : RgM_RgV_mul(GEN x, GEN y)
     451             : {
     452           0 :   if (lg(x) != 2) pari_err_OP("operation 'RgM_RgV_mul'", x,y);
     453           0 :   return RgC_RgV_mul(gel(x,1), y);
     454             : }
     455             : 
     456             : /* x[i,]*y, l = lg(y) > 1 */
     457             : static GEN
     458    33831661 : RgMrow_RgC_mul_i(GEN x, GEN y, long i, long l)
     459             : {
     460    33831661 :   pari_sp av = avma;
     461    33831661 :   GEN t = gmul(gcoeff(x,i,1), gel(y,1)); /* l > 1 ! */
     462             :   long j;
     463   308678318 :   for (j=2; j<l; j++) t = gadd(t, gmul(gcoeff(x,i,j), gel(y,j)));
     464    33831660 :   return gerepileupto(av,t);
     465             : }
     466             : GEN
     467        4494 : RgMrow_RgC_mul(GEN x, GEN y, long i)
     468        4494 : { return RgMrow_RgC_mul_i(x, y, i, lg(x)); }
     469             : 
     470             : static GEN
     471          28 : RgM_RgC_mul_FpM(GEN x, GEN y, GEN p)
     472             : {
     473          28 :   pari_sp av = avma;
     474             :   GEN r;
     475          28 :   if (lgefint(p) == 3)
     476             :   {
     477          14 :     ulong pp = uel(p, 2);
     478          14 :     r = Flc_to_ZC_inplace(Flm_Flc_mul(RgM_to_Flm(x, pp),
     479             :                                   RgV_to_Flv(y, pp), pp));
     480             :   }
     481             :   else
     482          14 :     r = FpM_FpC_mul(RgM_to_FpM(x, p), RgC_to_FpC(y, p), p);
     483          28 :   return gerepileupto(av, FpC_to_mod(r, p));
     484             : }
     485             : 
     486             : static GEN
     487          14 : RgM_RgC_mul_FqM(GEN x, GEN y, GEN pol, GEN p)
     488             : {
     489          14 :   pari_sp av = avma;
     490          14 :   GEN b, T = RgX_to_FpX(pol, p);
     491          14 :   if (signe(T) == 0) pari_err_OP("*", x, y);
     492          14 :   b = FqM_FqC_mul(RgM_to_FqM(x, T, p), RgC_to_FqC(y, T, p), T, p);
     493          14 :   return gerepileupto(av, FqC_to_mod(b, T, p));
     494             : }
     495             : 
     496             : #define code(t1,t2) ((t1 << 6) | t2)
     497             : static GEN
     498    11753292 : RgM_RgC_mul_fast(GEN x, GEN y)
     499             : {
     500             :   GEN p, pol;
     501             :   long pa;
     502    11753292 :   long t = RgM_RgC_type(x,y, &p,&pol,&pa);
     503    11753292 :   switch(t)
     504             :   {
     505     7803444 :     case t_INT:    return ZM_ZC_mul(x,y);
     506      116871 :     case t_FRAC:   return QM_QC_mul(x,y);
     507          91 :     case t_FFELT:  return FFM_FFC_mul(x, y, pol);
     508          28 :     case t_INTMOD: return RgM_RgC_mul_FpM(x, y, p);
     509          14 :     case code(t_POLMOD, t_INTMOD):
     510          14 :                    return RgM_RgC_mul_FqM(x, y, pol, p);
     511     3832844 :     default:       return NULL;
     512             :   }
     513             : }
     514             : #undef code
     515             : 
     516             : /* compatible t_MAT * t_COL, lx = lg(x) = lg(y) > 1, l = lgcols(x) */
     517             : static GEN
     518     8709679 : RgM_RgC_mul_i(GEN x, GEN y, long lx, long l)
     519             : {
     520     8709679 :   GEN z = cgetg(l,t_COL);
     521             :   long i;
     522    42536846 :   for (i=1; i<l; i++) gel(z,i) = RgMrow_RgC_mul_i(x,y,i,lx);
     523     8709679 :   return z;
     524             : }
     525             : 
     526             : GEN
     527    11753292 : RgM_RgC_mul(GEN x, GEN y)
     528             : {
     529    11753292 :   long lx = lg(x);
     530             :   GEN z;
     531    11753292 :   if (lx != lg(y)) pari_err_OP("operation 'RgM_RgC_mul'", x,y);
     532    11753292 :   if (lx == 1) return cgetg(1,t_COL);
     533    11753292 :   z = RgM_RgC_mul_fast(x, y);
     534    11753292 :   if (z) return z;
     535     3832844 :   return RgM_RgC_mul_i(x, y, lx, lgcols(x));
     536             : }
     537             : 
     538             : GEN
     539       64159 : RgV_RgM_mul(GEN x, GEN y)
     540             : {
     541       64159 :   long i, lx, ly = lg(y);
     542             :   GEN z;
     543       64159 :   if (ly == 1) return cgetg(1,t_VEC);
     544       64152 :   lx = lg(x);
     545       64152 :   if (lx != lgcols(y)) pari_err_OP("operation 'RgV_RgM_mul'", x,y);
     546       64145 :   z = cgetg(ly, t_VEC);
     547      912190 :   for (i=1; i<ly; i++) gel(z,i) = RgV_dotproduct_i(x, gel(y,i), lx);
     548       64145 :   return z;
     549             : }
     550             : 
     551             : static GEN
     552       56238 : RgM_mul_FpM(GEN x, GEN y, GEN p)
     553             : {
     554       56238 :   pari_sp av = avma;
     555             :   GEN r;
     556       56238 :   if (lgefint(p) == 3)
     557             :   {
     558       56166 :     ulong pp = uel(p, 2);
     559       56166 :     r = Flm_to_ZM_inplace(Flm_mul(RgM_to_Flm(x, pp),
     560             :                                   RgM_to_Flm(y, pp), pp));
     561             :   }
     562             :   else
     563          72 :     r = FpM_mul(RgM_to_FpM(x, p), RgM_to_FpM(y, p), p);
     564       56238 :   return gerepileupto(av, FpM_to_mod(r, p));
     565             : }
     566             : 
     567             : static GEN
     568       26019 : RgM_mul_FqM(GEN x, GEN y, GEN pol, GEN p)
     569             : {
     570       26019 :   pari_sp av = avma;
     571       26019 :   GEN b, T = RgX_to_FpX(pol, p);
     572       26019 :   if (signe(T) == 0) pari_err_OP("*", x, y);
     573       26019 :   b = FqM_mul(RgM_to_FqM(x, T, p), RgM_to_FqM(y, T, p), T, p);
     574       26019 :   return gerepileupto(av, FqM_to_mod(b, T, p));
     575             : }
     576             : 
     577             : static GEN
     578       14812 : RgM_liftred(GEN x, GEN T)
     579       14812 : { return RgXQM_red(liftpol_shallow(x), T); }
     580             : 
     581             : static GEN
     582        2765 : RgM_mul_ZXQM(GEN x, GEN y, GEN T)
     583             : {
     584        2765 :   pari_sp av = avma;
     585        2765 :   GEN b = ZXQM_mul(RgM_liftred(x,T), RgM_liftred(y, T), T);
     586        2765 :   return gerepilecopy(av, QXQM_to_mod_shallow(b,T));
     587             : }
     588             : 
     589             : static GEN
     590         133 : RgM_sqr_ZXQM(GEN x, GEN T)
     591             : {
     592         133 :   pari_sp av = avma;
     593         133 :   GEN b = ZXQM_sqr(RgM_liftred(x, T), T);
     594         133 :   return gerepilecopy(av, QXQM_to_mod_shallow(b,T));
     595             : }
     596             : 
     597             : static GEN
     598        4571 : RgM_mul_QXQM(GEN x, GEN y, GEN T)
     599             : {
     600        4571 :   pari_sp av = avma;
     601        4571 :   GEN b = QXQM_mul(RgM_liftred(x, T), RgM_liftred(y, T), T);
     602        4571 :   return gerepilecopy(av, QXQM_to_mod_shallow(b,T));
     603             : }
     604             : 
     605             : static GEN
     606           7 : RgM_sqr_QXQM(GEN x, GEN T)
     607             : {
     608           7 :   pari_sp av = avma;
     609           7 :   GEN b = QXQM_sqr(RgM_liftred(x, T), T);
     610           7 :   return gerepilecopy(av, QXQM_to_mod_shallow(b,T));
     611             : }
     612             : 
     613             : INLINE int
     614        4620 : RgX_is_monic_ZX(GEN pol)
     615        4620 : { return RgX_is_ZX(pol) && ZX_is_monic(pol); }
     616             : 
     617             : #define code(t1,t2) ((t1 << 6) | t2)
     618             : static GEN
     619     4842966 : RgM_mul_fast(GEN x, GEN y)
     620             : {
     621             :   GEN p, pol;
     622             :   long pa;
     623     4842966 :   long t = RgM_type2(x,y, &p,&pol,&pa);
     624     4842966 :   switch(t)
     625             :   {
     626     2654539 :     case t_INT:    return ZM_mul(x,y);
     627      139165 :     case t_FRAC:   return QM_mul(x,y);
     628        4200 :     case t_FFELT:  return FFM_mul(x, y, pol);
     629       56175 :     case t_INTMOD: return RgM_mul_FpM(x, y, p);
     630        2772 :     case code(t_POLMOD, t_INT):
     631        2772 :                    return ZX_is_monic(pol)? RgM_mul_ZXQM(x, y, pol): NULL;
     632        4592 :     case code(t_POLMOD, t_FRAC):
     633        4592 :                    return RgX_is_monic_ZX(pol)? RgM_mul_QXQM(x, y, pol): NULL;
     634       26019 :     case code(t_POLMOD, t_INTMOD):
     635       26019 :                    return RgM_mul_FqM(x, y, pol, p);
     636     1955504 :     default:       return NULL;
     637             :   }
     638             : }
     639             : 
     640             : static GEN
     641        1183 : RgM_sqr_fast(GEN x)
     642             : {
     643             :   GEN p, pol;
     644             :   long pa;
     645        1183 :   long t = RgM_type(x, &p,&pol,&pa);
     646        1183 :   switch(t)
     647             :   {
     648         126 :     case t_INT:    return ZM_sqr(x);
     649         700 :     case t_FRAC:   return QM_sqr(x);
     650         105 :     case t_FFELT:  return FFM_mul(x, x, pol);
     651          63 :     case t_INTMOD: return RgM_mul_FpM(x, x, p);
     652         140 :     case code(t_POLMOD, t_INT):
     653         140 :                    return ZX_is_monic(pol)? RgM_sqr_ZXQM(x, pol): NULL;
     654          28 :     case code(t_POLMOD, t_FRAC):
     655          28 :                    return RgX_is_monic_ZX(pol)? RgM_sqr_QXQM(x, pol): NULL;
     656           0 :     case code(t_POLMOD, t_INTMOD):
     657           0 :                    return RgM_mul_FqM(x, x, pol, p);
     658          21 :     default:       return NULL;
     659             :   }
     660             : }
     661             : 
     662             : #undef code
     663             : 
     664             : GEN
     665     4864982 : RgM_mul(GEN x, GEN y)
     666             : {
     667     4864982 :   long j, l, lx, ly = lg(y);
     668             :   GEN z;
     669     4864982 :   if (ly == 1) return cgetg(1,t_MAT);
     670     4842987 :   lx = lg(x);
     671     4842987 :   if (lx != lgcols(y)) pari_err_OP("operation 'RgM_mul'", x,y);
     672     4842987 :   if (lx == 1) return zeromat(0,ly-1);
     673     4842966 :   z = RgM_mul_fast(x, y);
     674     4842966 :   if (z) return z;
     675     1955532 :   z = cgetg(ly, t_MAT);
     676     1955532 :   l = lgcols(x);
     677     6832150 :   for (j=1; j<ly; j++) gel(z,j) = RgM_RgC_mul_i(x, gel(y,j), lx, l);
     678     1955532 :   return z;
     679             : }
     680             : 
     681             : GEN
     682        1218 : RgM_sqr(GEN x)
     683             : {
     684        1218 :   long j, lx = lg(x);
     685             :   GEN z;
     686        1218 :   if (lx == 1) return cgetg(1, t_MAT);
     687        1183 :   if (lx != lgcols(x)) pari_err_OP("operation 'RgM_mul'", x,x);
     688        1183 :   z = RgM_sqr_fast(x);
     689        1183 :   if (z) return z;
     690          49 :   z = cgetg(lx, t_MAT);
     691         266 :   for (j=1; j<lx; j++) gel(z,j) = RgM_RgC_mul_i(x, gel(x,j), lx, lx);
     692          49 :   return z;
     693             : }
     694             : 
     695             : /* assume result is symmetric */
     696             : GEN
     697           0 : RgM_multosym(GEN x, GEN y)
     698             : {
     699           0 :   long j, lx, ly = lg(y);
     700             :   GEN M;
     701           0 :   if (ly == 1) return cgetg(1,t_MAT);
     702           0 :   lx = lg(x);
     703           0 :   if (lx != lgcols(y)) pari_err_OP("operation 'RgM_multosym'", x,y);
     704           0 :   if (lx == 1) return cgetg(1,t_MAT);
     705           0 :   if (ly != lgcols(x)) pari_err_OP("operation 'RgM_multosym'", x,y);
     706           0 :   M = cgetg(ly, t_MAT);
     707           0 :   for (j=1; j<ly; j++)
     708             :   {
     709           0 :     GEN z = cgetg(ly,t_COL), yj = gel(y,j);
     710             :     long i;
     711           0 :     for (i=1; i<j; i++) gel(z,i) = gcoeff(M,j,i);
     712           0 :     for (i=j; i<ly; i++)gel(z,i) = RgMrow_RgC_mul_i(x,yj,i,lx);
     713           0 :     gel(M,j) = z;
     714             :   }
     715           0 :   return M;
     716             : }
     717             : /* x~ * y, assuming result is symmetric */
     718             : GEN
     719         496 : RgM_transmultosym(GEN x, GEN y)
     720             : {
     721         496 :   long i, j, l, ly = lg(y);
     722             :   GEN M;
     723         496 :   if (ly == 1) return cgetg(1,t_MAT);
     724         496 :   if (lg(x) != ly) pari_err_OP("operation 'RgM_transmultosym'", x,y);
     725         496 :   l = lgcols(y);
     726         496 :   if (lgcols(x) != l) pari_err_OP("operation 'RgM_transmultosym'", x,y);
     727         496 :   M = cgetg(ly, t_MAT);
     728        2215 :   for (i=1; i<ly; i++)
     729             :   {
     730        1719 :     GEN xi = gel(x,i), c = cgetg(ly,t_COL);
     731        1719 :     gel(M,i) = c;
     732        4712 :     for (j=1; j<i; j++)
     733        2993 :       gcoeff(M,i,j) = gel(c,j) = RgV_dotproduct_i(xi,gel(y,j),l);
     734        1719 :     gel(c,i) = RgV_dotproduct_i(xi,gel(y,i),l);
     735             :   }
     736         496 :   return M;
     737             : }
     738             : /* x~ * y */
     739             : GEN
     740           0 : RgM_transmul(GEN x, GEN y)
     741             : {
     742           0 :   long i, j, l, lx, ly = lg(y);
     743             :   GEN M;
     744           0 :   if (ly == 1) return cgetg(1,t_MAT);
     745           0 :   lx = lg(x);
     746           0 :   l = lgcols(y);
     747           0 :   if (lgcols(x) != l) pari_err_OP("operation 'RgM_transmul'", x,y);
     748           0 :   M = cgetg(ly, t_MAT);
     749           0 :   for (i=1; i<ly; i++)
     750             :   {
     751           0 :     GEN yi = gel(y,i), c = cgetg(lx,t_COL);
     752           0 :     gel(M,i) = c;
     753           0 :     for (j=1; j<lx; j++) gel(c,j) = RgV_dotproduct_i(yi,gel(x,j),l);
     754             :   }
     755           0 :   return M;
     756             : }
     757             : 
     758             : GEN
     759         119 : gram_matrix(GEN x)
     760             : {
     761         119 :   long i,j, l, lx = lg(x);
     762             :   GEN M;
     763         119 :   if (!is_matvec_t(typ(x))) pari_err_TYPE("gram",x);
     764         119 :   if (lx == 1) return cgetg(1,t_MAT);
     765         105 :   l = lgcols(x);
     766         105 :   M = cgetg(lx,t_MAT);
     767         294 :   for (i=1; i<lx; i++)
     768             :   {
     769         189 :     GEN xi = gel(x,i), c = cgetg(lx,t_COL);
     770         189 :     gel(M,i) = c;
     771         280 :     for (j=1; j<i; j++)
     772          91 :       gcoeff(M,i,j) = gel(c,j) = RgV_dotproduct_i(xi,gel(x,j),l);
     773         189 :     gel(c,i) = RgV_dotsquare(xi);
     774             :   }
     775         105 :   return M;
     776             : }
     777             : 
     778             : static GEN
     779        3542 : _RgM_add(void *E, GEN x, GEN y) { (void)E; return RgM_add(x, y); }
     780             : 
     781             : static GEN
     782           0 : _RgM_sub(void *E, GEN x, GEN y) { (void)E; return RgM_sub(x, y); }
     783             : 
     784             : static GEN
     785        5229 : _RgM_cmul(void *E, GEN P, long a, GEN x) { (void)E; return RgM_Rg_mul(x,gel(P,a+2)); }
     786             : 
     787             : static GEN
     788         238 : _RgM_sqr(void *E, GEN x) { (void) E; return RgM_sqr(x); }
     789             : 
     790             : static GEN
     791         686 : _RgM_mul(void *E, GEN x, GEN y) { (void) E; return RgM_mul(x, y); }
     792             : 
     793             : static GEN
     794        3591 : _RgM_one(void *E) { long *n = (long*) E; return matid(*n); }
     795             : 
     796             : static GEN
     797           0 : _RgM_zero(void *E) { long *n = (long*) E; return zeromat(*n,*n); }
     798             : 
     799             : static GEN
     800        2506 : _RgM_red(void *E, GEN x) { (void)E; return x; }
     801             : 
     802             : static struct bb_algebra RgM_algebra = { _RgM_red, _RgM_add, _RgM_sub,
     803             :        _RgM_mul, _RgM_sqr, _RgM_one, _RgM_zero };
     804             : 
     805             : /* generates the list of powers of x of degree 0,1,2,...,l*/
     806             : GEN
     807         168 : RgM_powers(GEN x, long l)
     808             : {
     809         168 :   long n = lg(x)-1;
     810         168 :   return gen_powers(x,l,1,(void *) &n, &_RgM_sqr, &_RgM_mul, &_RgM_one);
     811             : }
     812             : 
     813             : GEN
     814         490 : RgX_RgMV_eval(GEN Q, GEN x)
     815             : {
     816         490 :   long n = lg(x)>1 ? lg(gel(x,1))-1:0;
     817         490 :   return gen_bkeval_powers(Q,degpol(Q),x,(void*)&n,&RgM_algebra,&_RgM_cmul);
     818             : }
     819             : 
     820             : GEN
     821        1197 : RgX_RgM_eval(GEN Q, GEN x)
     822             : {
     823        1197 :   long n = lg(x)-1;
     824        1197 :   return gen_bkeval(Q,degpol(Q),x,1,(void*)&n,&RgM_algebra,&_RgM_cmul);
     825             : }
     826             : 
     827             : GEN
     828     1197036 : RgC_Rg_div(GEN x, GEN y)
     829     6246832 : { pari_APPLY_type(t_COL, gdiv(gel(x,i),y)) }
     830             : 
     831             : GEN
     832     6144476 : RgC_Rg_mul(GEN x, GEN y)
     833    35992725 : { pari_APPLY_type(t_COL, gmul(gel(x,i),y)) }
     834             : 
     835             : GEN
     836        6930 : RgV_Rg_mul(GEN x, GEN y)
     837      671342 : { pari_APPLY_type(t_VEC, gmul(gel(x,i),y)) }
     838             : 
     839             : GEN
     840      150706 : RgM_Rg_div(GEN X, GEN c) {
     841      150706 :   long i, j, h, l = lg(X);
     842      150706 :   GEN A = cgetg(l, t_MAT);
     843      150706 :   if (l == 1) return A;
     844      150706 :   h = lgcols(X);
     845      989856 :   for (j=1; j<l; j++)
     846             :   {
     847      839149 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     848    10425446 :     for (i = 1; i < h; i++) gel(a,i) = gdiv(gel(x,i), c);
     849      839150 :     gel(A,j) = a;
     850             :   }
     851      150707 :   return A;
     852             : }
     853             : GEN
     854      167244 : RgM_Rg_mul(GEN X, GEN c) {
     855      167244 :   long i, j, h, l = lg(X);
     856      167244 :   GEN A = cgetg(l, t_MAT);
     857      167244 :   if (l == 1) return A;
     858      166894 :   h = lgcols(X);
     859      827029 :   for (j=1; j<l; j++)
     860             :   {
     861      660135 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     862     6274128 :     for (i = 1; i < h; i++) gel(a,i) = gmul(gel(x,i), c);
     863      660135 :     gel(A,j) = a;
     864             :   }
     865      166894 :   return A;
     866             : }
     867             : 
     868             : /********************************************************************/
     869             : /*                                                                  */
     870             : /*                    SCALAR TO MATRIX/VECTOR                       */
     871             : /*                                                                  */
     872             : /********************************************************************/
     873             : /* fill the square nxn matrix equal to t*Id */
     874             : static void
     875     6071657 : fill_scalmat(GEN y, GEN t, long n)
     876             : {
     877             :   long i;
     878    22749295 :   for (i = 1; i <= n; i++)
     879             :   {
     880    16677618 :     gel(y,i) = zerocol(n);
     881    16677638 :     gcoeff(y,i,i) = t;
     882             :   }
     883     6071677 : }
     884             : 
     885             : GEN
     886      452347 : scalarmat(GEN x, long n) {
     887      452347 :   GEN y = cgetg(n+1, t_MAT);
     888      452347 :   if (!n) return y;
     889      452347 :   fill_scalmat(y, gcopy(x), n); return y;
     890             : }
     891             : GEN
     892     2040373 : scalarmat_shallow(GEN x, long n) {
     893     2040373 :   GEN y = cgetg(n+1, t_MAT);
     894     2040381 :   fill_scalmat(y, x, n); return y;
     895             : }
     896             : GEN
     897         175 : scalarmat_s(long x, long n) {
     898         175 :   GEN y = cgetg(n+1, t_MAT);
     899         175 :   if (!n) return y;
     900         175 :   fill_scalmat(y, stoi(x), n); return y;
     901             : }
     902             : GEN
     903     3578762 : matid(long n) {
     904             :   GEN y;
     905     3578762 :   if (n < 0) pari_err_DOMAIN("matid", "size", "<", gen_0, stoi(n));
     906     3578755 :   y = cgetg(n+1, t_MAT);
     907     3578755 :   fill_scalmat(y, gen_1, n); return y;
     908             : }
     909             : 
     910             : INLINE GEN
     911      428575 : scalarcol_i(GEN x, long n, long c)
     912             : {
     913             :   long i;
     914      428575 :   GEN y = cgetg(n+1,t_COL);
     915      428575 :   if (!n) return y;
     916      428575 :   gel(y,1) = c? gcopy(x): x;
     917     1558140 :   for (i=2; i<=n; i++) gel(y,i) = gen_0;
     918      428575 :   return y;
     919             : }
     920             : 
     921             : GEN
     922      149406 : scalarcol(GEN x, long n) { return scalarcol_i(x,n,1); }
     923             : 
     924             : GEN
     925      279169 : scalarcol_shallow(GEN x, long n) { return scalarcol_i(x,n,0); }
     926             : 
     927             : int
     928       26880 : RgM_isscalar(GEN x, GEN s)
     929             : {
     930       26880 :   long i, j, lx = lg(x);
     931             : 
     932       26880 :   if (lx == 1) return 1;
     933       26880 :   if (lx != lgcols(x)) return 0;
     934       26880 :   if (!s) s = gcoeff(x,1,1);
     935             : 
     936       70791 :   for (j=1; j<lx; j++)
     937             :   {
     938       56448 :     GEN c = gel(x,j);
     939       78547 :     for (i=1; i<j; )
     940       33061 :       if (!gequal0(gel(c,i++))) return 0;
     941             :     /* i = j */
     942       45486 :     if (!gequal(gel(c,i++),s)) return 0;
     943       80262 :     for (   ; i<lx; )
     944       36351 :       if (!gequal0(gel(c,i++))) return 0;
     945             :   }
     946       14343 :   return 1;
     947             : }
     948             : 
     949             : int
     950       12187 : RgM_isidentity(GEN x)
     951             : {
     952       12187 :   long i,j, lx = lg(x);
     953             : 
     954       12187 :   if (lx == 1) return 1;
     955       12187 :   if (lx != lgcols(x)) return 0;
     956       16975 :   for (j=1; j<lx; j++)
     957             :   {
     958       16828 :     GEN c = gel(x,j);
     959       18725 :     for (i=1; i<j; )
     960        5306 :       if (!gequal0(gel(c,i++))) return 0;
     961             :     /* i = j */
     962       13419 :     if (!gequal1(gel(c,i++))) return 0;
     963       11088 :     for (   ; i<lx; )
     964        6300 :       if (!gequal0(gel(c,i++))) return 0;
     965             :   }
     966         147 :   return 1;
     967             : }
     968             : 
     969             : long
     970         308 : RgC_is_ei(GEN x)
     971             : {
     972         308 :   long i, j = 0, l = lg(x);
     973        1792 :   for (i = 1; i < l; i++)
     974             :   {
     975        1484 :     GEN c = gel(x,i);
     976        1484 :     if (gequal0(c)) continue;
     977         308 :     if (!gequal1(c) || j) return 0;
     978         308 :     j = i;
     979             :   }
     980         308 :   return j;
     981             : }
     982             : 
     983             : int
     984         336 : RgM_isdiagonal(GEN x)
     985             : {
     986         336 :   long i,j, lx = lg(x);
     987         336 :   if (lx == 1) return 1;
     988         336 :   if (lx != lgcols(x)) return 0;
     989             : 
     990        3220 :   for (j=1; j<lx; j++)
     991             :   {
     992        2891 :     GEN c = gel(x,j);
     993       18452 :     for (i=1; i<j; i++)
     994       15561 :       if (!gequal0(gel(c,i))) return 0;
     995       18452 :     for (i++; i<lx; i++)
     996       15568 :       if (!gequal0(gel(c,i))) return 0;
     997             :   }
     998         329 :   return 1;
     999             : }
    1000             : int
    1001         315 : isdiagonal(GEN x) { return (typ(x)==t_MAT) && RgM_isdiagonal(x); }
    1002             : 
    1003             : GEN
    1004       16097 : RgM_det_triangular(GEN mat)
    1005             : {
    1006       16097 :   long i,l = lg(mat);
    1007             :   pari_sp av;
    1008             :   GEN s;
    1009             : 
    1010       16097 :   if (l<3) return l<2? gen_1: gcopy(gcoeff(mat,1,1));
    1011       14914 :   av = avma; s = gcoeff(mat,1,1);
    1012       99980 :   for (i=2; i<l; i++) s = gmul(s,gcoeff(mat,i,i));
    1013       14914 :   return av==avma? gcopy(s): gerepileupto(av,s);
    1014             : }
    1015             : 
    1016             : GEN
    1017       29852 : RgV_kill0(GEN v)
    1018             : {
    1019             :   long i, l;
    1020       29852 :   GEN w = cgetg_copy(v, &l);
    1021    11386159 :   for (i = 1; i < l; i++)
    1022             :   {
    1023    11356851 :     GEN a = gel(v,i);
    1024    11356851 :     gel(w,i) = gequal0(a) ? NULL: a;
    1025             :   }
    1026       29308 :   return w;
    1027             : }

Generated by: LCOV version 1.13