bridge/class-master/depend/pari/src/basemath/alglin1.c
/* solve X*U = B,  U upper triangular and invertible */
solve X*U = B,  U upper triangular and invertible
solve X * U = B U upper triangular and invertible
static GEN
Flm_lsolve_upper(GEN U, GEN B, ulong p)
{
  long n = lg(U) - 1, n1;
  GEN U2, U11, U12, U22, B1, B2, X1, X2, X;
  pari_sp av = avma;
  if (n == 0) return B;
  if (n == 1) return Flm_lsolve_upper_1(U, B, p);
  if (n == 2) return Flm_lsolve_upper_2(U, B, p);
  n1 = (n + 1)/2;
  U2 = vecslice(U, n1 + 1, n);
  U11 = matslice(U, 1,n1, 1,n1);
  U12 = rowslice(U2, 1, n1);
  U22 = rowslice(U2, n1 + 1, n);
  B1 = vecslice(B, 1, n1);
  B2 = vecslice(B, n1 + 1, n);
  X1 = Flm_lsolve_upper(U11, B1, p);
  B2 = Flm_sub(B2, Flm_mul(X1, U12, p), p);
  if (gc_needed(av, 1)) gerepileall(av, 3, &B2, &U22, &X1);
  X2 = Flm_lsolve_upper(U22, B2, p);
  X = shallowconcat(X1, X2);
  if (gc_needed(av, 1)) X = gerepilecopy(av, X);
  return X;
}
static GEN Flm_lsolve_upper ( GEN U , GEN B , ulong p ) { long n = lg ( U ) - 1 , n1 ; GEN U2 , U11 , U12 , U22 , B1 , B2 , X1 , X2 , X ; pari_sp av = avma ; if ( n == 0 ) return B ; if ( n == 1 ) return Flm_lsolve_upper_1 ( U , B , p ) ; if ( n == 2 ) return Flm_lsolve_upper_2 ( U , B , p ) ; n1 = ( n + 1 ) / 2 ; U2 = vecslice ( U , n1 + 1 , n ) ; U11 = matslice ( U , 1 , n1 , 1 , n1 ) ; U12 = rowslice ( U2 , 1 , n1 ) ; U22 = rowslice ( U2 , n1 + 1 , n ) ; B1 = vecslice ( B , 1 , n1 ) ; B2 = vecslice ( B , n1 + 1 , n ) ; X1 = Flm_lsolve_upper ( U11 , B1 , p ) ; B2 = Flm_sub ( B2 , Flm_mul ( X1 , U12 , p ) , p ) ; if ( gc_needed ( av , 1 ) ) gerepileall ( av , 3 , & B2 , & U22 , & X1 ) ; X2 = Flm_lsolve_upper ( U22 , B2 , p ) ; X = shallowconcat ( X1 , X2 ) ; if ( gc_needed ( av , 1 ) ) X = gerepilecopy ( av , X ) ; return X ; }
solve X*U = B,  U upper triangular and invertible
solve X * U = B U upper triangular and invertible