My Project
Loading...
Searching...
No Matches
Public Member Functions | Private Member Functions | Private Attributes
sparse_number_mat Class Reference

Public Member Functions

 sparse_number_mat (ideal, const ring)
 
 ~sparse_number_mat ()
 
int smIsSing ()
 
void smTriangular ()
 
void smSolv ()
 
ideal smRes2Ideal ()
 

Private Member Functions

void smColToRow ()
 
void smRowToCol ()
 
void smSelectPR ()
 
void smRealPivot ()
 
void smZeroToredElim ()
 
void smGElim ()
 
void smAllDel ()
 

Private Attributes

int nrows
 
int ncols
 
int act
 
int crd
 
int tored
 
int sing
 
int rpiv
 
int * perm
 
number * sol
 
int * wrw
 
int * wcl
 
smnumberm_act
 
smnumberm_res
 
smnumberm_row
 
smnumber red
 
smnumber piv
 
smnumber dumm
 
ring _R
 

Detailed Description

Definition at line 2275 of file sparsmat.cc.

Constructor & Destructor Documentation

◆ sparse_number_mat()

sparse_number_mat::sparse_number_mat ( ideal  smat,
const ring  R 
)

Definition at line 2351 of file sparsmat.cc.

2352{
2353 int i;
2354 poly* pmat;
2355 _R=R;
2356
2357 crd = sing = 0;
2358 act = ncols = smat->ncols;
2359 tored = nrows = smat->rank;
2360 i = tored+1;
2361 perm = (int *)omAlloc(sizeof(int)*i);
2362 m_row = (smnumber *)omAlloc0(sizeof(smnumber)*i);
2363 wrw = (int *)omAlloc(sizeof(int)*i);
2364 i = ncols+1;
2365 wcl = (int *)omAlloc(sizeof(int)*i);
2366 m_act = (smnumber *)omAlloc(sizeof(smnumber)*i);
2367 m_res = (smnumber *)omAlloc0(sizeof(smnumber)*i);
2369 pmat = smat->m;
2370 for(i=ncols; i; i--)
2371 {
2372 m_act[i] = sm_Poly2Smnumber(pmat[i-1],_R);
2373 }
2374 omFreeSize((ADDRESS)pmat,smat->ncols*sizeof(poly));
2376}
void * ADDRESS
Definition: auxiliary.h:119
int i
Definition: cfEzgcd.cc:132
smnumber * m_act
Definition: sparsmat.cc:2286
smnumber * m_res
Definition: sparsmat.cc:2287
smnumber * m_row
Definition: sparsmat.cc:2288
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
#define omAlloc0(size)
Definition: omAllocDecl.h:211
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
VAR omBin sip_sideal_bin
Definition: simpleideals.cc:27
#define R
Definition: sirandom.c:27
STATIC_VAR omBin smnrec_bin
Definition: sparsmat.cc:2264
static smnumber sm_Poly2Smnumber(poly, const ring)
Definition: sparsmat.cc:2845
sm_nrec * smnumber
Definition: sparsmat.cc:2257

◆ ~sparse_number_mat()

sparse_number_mat::~sparse_number_mat ( )

Definition at line 2381 of file sparsmat.cc.

2382{
2383 int i;
2385 i = ncols+1;
2386 omFreeSize((ADDRESS)m_res, sizeof(smnumber)*i);
2387 omFreeSize((ADDRESS)m_act, sizeof(smnumber)*i);
2388 omFreeSize((ADDRESS)wcl, sizeof(int)*i);
2389 i = nrows+1;
2390 omFreeSize((ADDRESS)wrw, sizeof(int)*i);
2391 omFreeSize((ADDRESS)m_row, sizeof(smnumber)*i);
2392 omFreeSize((ADDRESS)perm, sizeof(int)*i);
2393}

Member Function Documentation

◆ smAllDel()

void sparse_number_mat::smAllDel ( )
private

Definition at line 2795 of file sparsmat.cc.

2796{
2797 smnumber a;
2798 int i;
2799
2800 for (i=act; i; i--)
2801 {
2802 a = m_act[i];
2803 while (a != NULL)
2804 sm_NumberDelete(&a,_R);
2805 }
2806 for (i=crd; i; i--)
2807 {
2808 a = m_res[i];
2809 while (a != NULL)
2810 sm_NumberDelete(&a,_R);
2811 }
2812 if (act)
2813 {
2814 for (i=nrows; i; i--)
2815 {
2816 a = m_row[i];
2817 while (a != NULL)
2818 sm_NumberDelete(&a,_R);
2819 }
2820 }
2821}
#define NULL
Definition: omList.c:12
static void sm_NumberDelete(smnumber *, const ring R)
Definition: sparsmat.cc:2825

◆ smColToRow()

void sparse_number_mat::smColToRow ( )
private

Definition at line 2720 of file sparsmat.cc.

2721{
2722 smnumber c = m_act[act];
2723 smnumber h;
2724
2725 while (c != NULL)
2726 {
2727 h = c;
2728 c = c->n;
2729 h->n = m_row[h->pos];
2730 m_row[h->pos] = h;
2731 h->pos = crd;
2732 }
2733}
STATIC_VAR Poly * h
Definition: janet.cc:971

◆ smGElim()

void sparse_number_mat::smGElim ( )
private

Definition at line 2576 of file sparsmat.cc.

2577{
2578 number p = n_Invers(piv->m,_R->cf); // pivotelement
2579 smnumber c = m_act[act]; // pivotcolumn
2580 smnumber r = red; // row to reduce
2581 smnumber res, a, b;
2582 number w, ha, hb;
2583
2584 if ((c == NULL) || (r == NULL))
2585 {
2586 while (r!=NULL) sm_NumberDelete(&r,_R);
2587 return;
2588 }
2589 do
2590 {
2591 a = m_act[r->pos];
2592 res = dumm;
2593 res->n = NULL;
2594 b = c;
2595 w = n_Mult(r->m, p,_R->cf);
2596 n_Delete(&r->m,_R->cf);
2597 r->m = w;
2598 loop // combine the chains a and b: a + w*b
2599 {
2600 if (a == NULL)
2601 {
2602 do
2603 {
2604 res = res->n = smNumberCopy(b);
2605 res->m = n_Mult(b->m, w,_R->cf);
2606 b = b->n;
2607 } while (b != NULL);
2608 break;
2609 }
2610 if (a->pos < b->pos)
2611 {
2612 res = res->n = a;
2613 a = a->n;
2614 }
2615 else if (a->pos > b->pos)
2616 {
2617 res = res->n = smNumberCopy(b);
2618 res->m = n_Mult(b->m, w,_R->cf);
2619 b = b->n;
2620 }
2621 else
2622 {
2623 hb = n_Mult(b->m, w,_R->cf);
2624 ha = n_Add(a->m, hb,_R->cf);
2625 n_Delete(&hb,_R->cf);
2626 n_Delete(&a->m,_R->cf);
2627 if (n_IsZero(ha,_R->cf))
2628 {
2629 sm_NumberDelete(&a,_R);
2630 }
2631 else
2632 {
2633 a->m = ha;
2634 res = res->n = a;
2635 a = a->n;
2636 }
2637 b = b->n;
2638 }
2639 if (b == NULL)
2640 {
2641 res->n = a;
2642 break;
2643 }
2644 }
2645 m_act[r->pos] = dumm->n;
2646 sm_NumberDelete(&r,_R);
2647 } while (r != NULL);
2648 n_Delete(&p,_R->cf);
2649}
int p
Definition: cfModGcd.cc:4078
CanonicalForm b
Definition: cfModGcd.cc:4103
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition: coeffs.h:633
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of 'a' and 'b', i.e., a+b
Definition: coeffs.h:647
static FORCE_INLINE number n_Invers(number a, const coeffs r)
return the multiplicative inverse of 'a'; raise an error if 'a' is not invertible
Definition: coeffs.h:561
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:461
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:452
CanonicalForm res
Definition: facAbsFact.cc:60
const CanonicalForm & w
Definition: facAbsFact.cc:51
static smnumber smNumberCopy(smnumber)
Definition: sparsmat.cc:2834
#define loop
Definition: structs.h:75

◆ smIsSing()

int sparse_number_mat::smIsSing ( )
inline

Definition at line 2303 of file sparsmat.cc.

2303{ return sing; }

◆ smRealPivot()

void sparse_number_mat::smRealPivot ( )
private

Definition at line 2525 of file sparsmat.cc.

2526{
2527 smnumber a;
2528 number x, xo;
2529 int i, copt, ropt;
2530
2531 xo=n_Init(0,_R->cf);
2532 for (i=act; i; i--)
2533 {
2534 a = m_act[i];
2535 while ((a!=NULL) && (a->pos<=tored))
2536 {
2537 x = a->m;
2538 if (n_GreaterZero(x,_R->cf))
2539 {
2540 if (n_Greater(x,xo,_R->cf))
2541 {
2542 n_Delete(&xo,_R->cf);
2543 xo = n_Copy(x,_R->cf);
2544 copt = i;
2545 ropt = a->pos;
2546 }
2547 }
2548 else
2549 {
2550 xo = n_InpNeg(xo,_R->cf);
2551 if (n_Greater(xo,x,_R->cf))
2552 {
2553 n_Delete(&xo,_R->cf);
2554 xo = n_Copy(x,_R->cf);
2555 copt = i;
2556 ropt = a->pos;
2557 }
2558 xo = n_InpNeg(xo,_R->cf);
2559 }
2560 a = a->n;
2561 }
2562 }
2563 rpiv = ropt;
2564 if (copt != act)
2565 {
2566 a = m_act[act];
2567 m_act[act] = m_act[copt];
2568 m_act[copt] = a;
2569 }
2570 n_Delete(&xo,_R->cf);
2571}
Variable x
Definition: cfModGcd.cc:4082
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition: coeffs.h:448
static FORCE_INLINE BOOLEAN n_GreaterZero(number n, const coeffs r)
ordered fields: TRUE iff 'n' is positive; in Z/pZ: TRUE iff 0 < m <= roundedBelow(p/2),...
Definition: coeffs.h:491
static FORCE_INLINE number n_InpNeg(number n, const coeffs r)
in-place negation of n MUST BE USED: n = n_InpNeg(n) (no copy is returned)
Definition: coeffs.h:554
static FORCE_INLINE BOOLEAN n_Greater(number a, number b, const coeffs r)
ordered fields: TRUE iff 'a' is larger than 'b'; in Z/pZ: TRUE iff la > lb, where la and lb are the l...
Definition: coeffs.h:508
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:535

◆ smRes2Ideal()

ideal sparse_number_mat::smRes2Ideal ( )

Definition at line 2506 of file sparsmat.cc.

2507{
2508 int i, j;
2509 ideal res = idInit(crd, 1);
2510
2511 for (i=crd; i; i--)
2512 {
2513 j = perm[i]-1;
2514 res->m[j] = sm_Smnumber2Poly(sol[i],_R);
2515 }
2516 omFreeSize((ADDRESS)sol, sizeof(number)*(crd+1));
2517 return res;
2518}
int j
Definition: facHensel.cc:110
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
static poly sm_Smnumber2Poly(number, const ring)
Definition: sparsmat.cc:2876

◆ smRowToCol()

void sparse_number_mat::smRowToCol ( )
private

Definition at line 2740 of file sparsmat.cc.

2741{
2742 smnumber r = m_row[rpiv];
2743 smnumber a, ap, h;
2744
2745 m_row[rpiv] = NULL;
2746 perm[crd] = rpiv;
2747 piv->pos = crd;
2748 m_res[crd] = piv;
2749 while (r != NULL)
2750 {
2751 ap = m_res[r->pos];
2752 loop
2753 {
2754 a = ap->n;
2755 if (a == NULL)
2756 {
2757 ap->n = h = r;
2758 r = r->n;
2759 h->n = a;
2760 h->pos = crd;
2761 break;
2762 }
2763 ap = a;
2764 }
2765 }
2766}
Definition: ap.h:40

◆ smSelectPR()

void sparse_number_mat::smSelectPR ( )
private

Definition at line 2656 of file sparsmat.cc.

2657{
2658 smnumber b = dumm;
2659 smnumber a, ap;
2660 int i;
2661
2662 if (TEST_OPT_PROT)
2663 {
2664 if ((crd+1)%10)
2665 PrintS(".");
2666 else
2667 PrintS(".\n");
2668 }
2669 a = m_act[act];
2670 if (a->pos < rpiv)
2671 {
2672 do
2673 {
2674 ap = a;
2675 a = a->n;
2676 } while (a->pos < rpiv);
2677 ap->n = a->n;
2678 }
2679 else
2680 m_act[act] = a->n;
2681 piv = a;
2682 a->n = NULL;
2683 for (i=1; i<act; i++)
2684 {
2685 a = m_act[i];
2686 if (a->pos < rpiv)
2687 {
2688 loop
2689 {
2690 ap = a;
2691 a = a->n;
2692 if ((a == NULL) || (a->pos > rpiv))
2693 break;
2694 if (a->pos == rpiv)
2695 {
2696 ap->n = a->n;
2697 a->m = n_InpNeg(a->m,_R->cf);
2698 b = b->n = a;
2699 b->pos = i;
2700 break;
2701 }
2702 }
2703 }
2704 else if (a->pos == rpiv)
2705 {
2706 m_act[i] = a->n;
2707 a->m = n_InpNeg(a->m,_R->cf);
2708 b = b->n = a;
2709 b->pos = i;
2710 }
2711 }
2712 b->n = NULL;
2713 red = dumm->n;
2714}
#define TEST_OPT_PROT
Definition: options.h:104
void PrintS(const char *s)
Definition: reporter.cc:284

◆ smSolv()

void sparse_number_mat::smSolv ( )

Definition at line 2429 of file sparsmat.cc.

2430{
2431 int i, j;
2432 number x, y, z;
2433 smnumber s, d, r = m_row[nrows];
2434
2435 m_row[nrows] = NULL;
2436 sol = (number *)omAlloc0(sizeof(number)*(crd+1));
2437 while (r != NULL) // expand the rigth hand side
2438 {
2439 sol[r->pos] = r->m;
2440 s = r;
2441 r = r->n;
2443 }
2444 i = crd; // solve triangular system
2445 if (sol[i] != NULL)
2446 {
2447 x = sol[i];
2448 sol[i] = n_Div(x, m_res[i]->m,_R->cf);
2449 n_Delete(&x,_R->cf);
2450 }
2451 i--;
2452 while (i > 0)
2453 {
2454 x = NULL;
2455 d = m_res[i];
2456 s = d->n;
2457 while (s != NULL)
2458 {
2459 j = s->pos;
2460 if (sol[j] != NULL)
2461 {
2462 z = n_Mult(sol[j], s->m,_R->cf);
2463 if (x != NULL)
2464 {
2465 y = x;
2466 x = n_Sub(y, z,_R->cf);
2467 n_Delete(&y,_R->cf);
2468 n_Delete(&z,_R->cf);
2469 }
2470 else
2471 x = n_InpNeg(z,_R->cf);
2472 }
2473 s = s->n;
2474 }
2475 if (sol[i] != NULL)
2476 {
2477 if (x != NULL)
2478 {
2479 y = n_Add(x, sol[i],_R->cf);
2480 n_Delete(&x,_R->cf);
2481 if (n_IsZero(y,_R->cf))
2482 {
2483 n_Delete(&sol[i],_R->cf);
2484 sol[i] = NULL;
2485 }
2486 else
2487 sol[i] = y;
2488 }
2489 }
2490 else
2491 sol[i] = x;
2492 if (sol[i] != NULL)
2493 {
2494 x = sol[i];
2495 sol[i] = n_Div(x, d->m,_R->cf);
2496 n_Delete(&x,_R->cf);
2497 }
2498 i--;
2499 }
2500 this->smAllDel();
2501}
int m
Definition: cfEzgcd.cc:128
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of 'a' and 'b', i.e., a/b; raises an error if 'b' is not invertible in r exceptio...
Definition: coeffs.h:612
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of 'a' and 'b', i.e., a-b
Definition: coeffs.h:652
const CanonicalForm int s
Definition: facAbsFact.cc:51
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53

◆ smTriangular()

void sparse_number_mat::smTriangular ( )

Definition at line 2398 of file sparsmat.cc.

2399{
2400 tored--;
2401 this->smZeroToredElim();
2402 if (sing != 0) return;
2403 while (act > 1)
2404 {
2405 this->smRealPivot();
2406 this->smSelectPR();
2407 this->smGElim();
2408 crd++;
2409 this->smColToRow();
2410 act--;
2411 this->smRowToCol();
2412 this->smZeroToredElim();
2413 if (sing != 0) return;
2414 }
2415 if (TEST_OPT_PROT) PrintS(".\n");
2416 piv = m_act[1];
2417 rpiv = piv->pos;
2418 m_act[1] = piv->n;
2419 piv->n = NULL;
2420 crd++;
2421 this->smColToRow();
2422 act--;
2423 this->smRowToCol();
2424}
void smZeroToredElim()
Definition: sparsmat.cc:2773

◆ smZeroToredElim()

void sparse_number_mat::smZeroToredElim ( )
private

Definition at line 2773 of file sparsmat.cc.

2774{
2775 smnumber a;
2776 int i = act;
2777
2778 loop
2779 {
2780 if (i == 0) return;
2781 a = m_act[i];
2782 if ((a==NULL) || (a->pos>tored))
2783 {
2784 sing = 1;
2785 this->smAllDel();
2786 return;
2787 }
2788 i--;
2789 }
2790}

Field Documentation

◆ _R

ring sparse_number_mat::_R
private

Definition at line 2292 of file sparsmat.cc.

◆ act

int sparse_number_mat::act
private

Definition at line 2278 of file sparsmat.cc.

◆ crd

int sparse_number_mat::crd
private

Definition at line 2279 of file sparsmat.cc.

◆ dumm

smnumber sparse_number_mat::dumm
private

Definition at line 2291 of file sparsmat.cc.

◆ m_act

smnumber* sparse_number_mat::m_act
private

Definition at line 2286 of file sparsmat.cc.

◆ m_res

smnumber* sparse_number_mat::m_res
private

Definition at line 2287 of file sparsmat.cc.

◆ m_row

smnumber* sparse_number_mat::m_row
private

Definition at line 2288 of file sparsmat.cc.

◆ ncols

int sparse_number_mat::ncols
private

Definition at line 2277 of file sparsmat.cc.

◆ nrows

int sparse_number_mat::nrows
private

Definition at line 2277 of file sparsmat.cc.

◆ perm

int* sparse_number_mat::perm
private

Definition at line 2283 of file sparsmat.cc.

◆ piv

smnumber sparse_number_mat::piv
private

Definition at line 2290 of file sparsmat.cc.

◆ red

smnumber sparse_number_mat::red
private

Definition at line 2289 of file sparsmat.cc.

◆ rpiv

int sparse_number_mat::rpiv
private

Definition at line 2282 of file sparsmat.cc.

◆ sing

int sparse_number_mat::sing
private

Definition at line 2281 of file sparsmat.cc.

◆ sol

number* sparse_number_mat::sol
private

Definition at line 2284 of file sparsmat.cc.

◆ tored

int sparse_number_mat::tored
private

Definition at line 2280 of file sparsmat.cc.

◆ wcl

int * sparse_number_mat::wcl
private

Definition at line 2285 of file sparsmat.cc.

◆ wrw

int* sparse_number_mat::wrw
private

Definition at line 2285 of file sparsmat.cc.


The documentation for this class was generated from the following file: