Changeset 83f349c in git


Ignore:
Timestamp:
Nov 6, 2009, 12:21:52 PM (14 years ago)
Author:
Frank Seelisch <seelisch@…>
Branches:
(u'spielwiese', '5d369c3cbad1a1bf2d5c856a48fb8a30b51cec3b')
Children:
1e673422a85a7bbfd9b52b229b919da1922c36e1
Parents:
dbee17cfa7cef0b7d7eee146e4e3183125034ea1
Message:

git-svn-id: file:///usr/local/Singular/svn/trunk@12250 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
Singular
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • Singular/Minor.h

    rdbee17c r83f349c  
    658658             PolyMinorValue (const PolyMinorValue& mv);
    659659             
     660             /* deep copy */
    660661             void operator= (const PolyMinorValue& mv);
    661662

  • Singular/MinorProcessor.cc

    rdbee17c r83f349c  
    184184}
    185185
    186 MinorProcessor::MinorProcessor () {         
     186MinorProcessor::MinorProcessor () {
    187187    _container = MinorKey(0, 0, 0, 0);
    188188    _minor = MinorKey(0, 0, 0, 0);
    … …  
    315315            for (int c = 0; c < k; c++) {
    316316                int absoluteC = mk.getAbsoluteColumnIndex(c);      // This iterates over all involved columns.
    317                 MinorKey subMk = mk.getSubMinorKey(b, absoluteC);  // This is MinorKey when we omit row b and column absoluteC.
    318317                if (_matrix[b][absoluteC] != 0) { // Only then do we have to consider this sub-determinante.
     318                    MinorKey subMk = mk.getSubMinorKey(b, absoluteC);  // This is mk with row b and column absoluteC omitted.
    319319                    IntMinorValue mv = getMinorPrivate(k - 1, subMk, characteristic);  // recursive call
    320320                    m += mv.getMultiplications();
    … …  
    338338            for (int r = 0; r < k; r++) {
    339339                int absoluteR = mk.getAbsoluteRowIndex(r);        // This iterates over all involved rows.
    340                 MinorKey subMk = mk.getSubMinorKey(absoluteR, b); // This is MinorKey when we omit row absoluteR and column b.
    341340                if (_matrix[absoluteR][b] != 0) { // Only then do we have to consider this sub-determinante.
     341                    MinorKey subMk = mk.getSubMinorKey(absoluteR, b); // This is mk with row absoluteR and column b omitted.
    342342                    IntMinorValue mv = getMinorPrivate(k - 1, subMk, characteristic);  // recursive call
    343343                    m += mv.getMultiplications();
    … …  
    386386            for (int c = 0; c < k; c++) {
    387387                int absoluteC = mk.getAbsoluteColumnIndex(c);      // This iterates over all involved columns.
    388                 MinorKey subMk = mk.getSubMinorKey(b, absoluteC);  // This is MinorKey when we omit row b and column absoluteC.
    389388                if (_matrix[b][absoluteC] != 0) { // Only then do we have to consider this sub-determinante.
     389                    MinorKey subMk = mk.getSubMinorKey(b, absoluteC);  // This is mk with row b and column absoluteC omitted.
    390390                    if (cch.hasKey(subMk)) { // trying to find the result in the cache
    391391                        mv = cch.getValue(subMk);
    … …  
    420420            for (int r = 0; r < k; r++) {
    421421                int absoluteR = mk.getAbsoluteRowIndex(r);        // This iterates over all involved rows.
    422                 MinorKey subMk = mk.getSubMinorKey(absoluteR, b); // This is MinorKey when we omit row absoluteR and column b.
    423422                if (_matrix[absoluteR][b] != 0) { // Only then do we have to consider this sub-determinante.
     423                    MinorKey subMk = mk.getSubMinorKey(absoluteR, b); // This is mk with row absoluteR and column b omitted.
    424424                    if (cch.hasKey(subMk)) { // trying to find the result in the cache
    425425                        mv = cch.getValue(subMk);
    … …  
    554554}
    555555
    556 // performs the assignment a = a + (b * c * d)
    557 // c and d must neither be destroyed nor modified
    558 // the old value of a and b will be destroyed
    559 // a will finally contain the new value
    560 void ops(poly a, poly b, poly c, poly d)
    561 {
    562   a = p_Add_q(a, p_Mult_q(b, pp_Mult_qq(c, d, currRing), currRing), currRing);
    563 }
    564 
    565556PolyMinorValue PolyMinorProcessor::getMinorPrivate(const int k, const MinorKey& mk) {
    566557    assert(k > 0); // k is the minor's dimension; the minor must be at least 1x1
    … …  
    574565        // Here, the minor must be 2x2 or larger.
    575566        int b = getBestLine(k, mk);                          // row or column with most zeros
    576         poly result = pISet(0);                              // This will contain the value of the minor.
     567        poly result = NULL;                                  // This will contain the value of the minor.
    577568        int s = 0; int m = 0; int as = 0; int am = 0;        // counters for additions and multiplications,
    578569                                                             // ..."a*" for accumulated operation counters
    … …  
    585576            for (int c = 0; c < k; c++) {
    586577                int absoluteC = mk.getAbsoluteColumnIndex(c);      // This iterates over all involved columns.
    587                 MinorKey subMk = mk.getSubMinorKey(b, absoluteC);  // This is MinorKey when we omit row b and column absoluteC.
    588578                if (!isEntryZero(b, absoluteC)) { // Only then do we have to consider this sub-determinante.
     579                    MinorKey subMk = mk.getSubMinorKey(b, absoluteC);  // This is MinorKey with row b and column absoluteC omitted.
    589580                    PolyMinorValue mv = getMinorPrivate(k - 1, subMk);  // recursive call
    590581                    m += mv.getMultiplications();
    … …  
    594585                    pDelete(&signPoly);
    595586                    signPoly = pISet(sign);
    596                     ops(result, signPoly, mv.getResult(), _polyMatrix[b][absoluteC]); // adding in "result" the product of sign,
    597                                                                                       // sub-determinante, and matrix entry
     587                    poly temp = pp_Mult_qq(mv.getResult(), _polyMatrix[b][absoluteC], currRing);
     588                    temp = p_Mult_q(signPoly, temp, currRing);
     589                    result = p_Add_q(result, temp, currRing);
    598590                    signPoly = NULL;
    599591                    s++; m++; as++, am++; // This is for the addition and multiplication in the previous line of code.
    … …  
    611603            for (int r = 0; r < k; r++) {
    612604                int absoluteR = mk.getAbsoluteRowIndex(r);        // This iterates over all involved rows.
    613                 MinorKey subMk = mk.getSubMinorKey(absoluteR, b); // This is MinorKey when we omit row absoluteR and column b.
    614605                if (!isEntryZero(absoluteR, b)) { // Only then do we have to consider this sub-determinante.
     606                    MinorKey subMk = mk.getSubMinorKey(absoluteR, b); // This is MinorKey with row absoluteR and column b omitted.
    615607                    PolyMinorValue mv = getMinorPrivate(k - 1, subMk);  // recursive call
    616608                    m += mv.getMultiplications();
    … …  
    620612                    pDelete(&signPoly);
    621613                    signPoly = pISet(sign);
    622                     ops(result, signPoly, mv.getResult(), _polyMatrix[absoluteR][b]); // adding in "result" the product of sign,
    623                                                                                       // sub-determinante, and matrix entry
     614                    poly temp = pp_Mult_qq(mv.getResult(), _polyMatrix[absoluteR][b], currRing);
     615                    temp = p_Mult_q(signPoly, temp, currRing);
     616                    result = p_Add_q(result, temp, currRing);
    624617                    signPoly = NULL;
    625618                    s++; m++; as++, am++; // This is for the addition and multiplication in the previous line of code.
    … …  
    634627                                                            // number of retrievals does not make sense, as we
    635628                                                            // do not use a cache.
     629//printf("\nMINOR to put: %s", pString(result));
    636630        pDelete(&result);
    637631        return newMV;
    … …  
    642636                                                   const bool multipleMinors,
    643637                                                   Cache<MinorKey, PolyMinorValue>& cch) {
     638//omUpdateInfo(); printf("\nused bytes: %12ld, called: %s  (k = %d)", om_Info.UsedBytes, "getMinorPrivate", k);
    644639    assert(k > 0); // k is the minor's dimension; the minor must be at least 1x1
    645640    // The method works by recursion, and using Lapace's Theorem along the row/column with the most zeros.
    … …  
    650645    else {
    651646        int b = getBestLine(k, mk);                          // row or column with most zeros
    652         poly result = pISet(0);                              // This will contain the value of the minor.
     647        poly result = NULL;                                  // This will contain the value of the minor.
     648//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d)", om_Info.UsedBytes, "poly result = NULL;", k);
    653649        int s = 0; int m = 0; int as = 0; int am = 0;        // counters for additions and multiplications,
    654650                                                             // ..."a*" for accumulated operation counters
    … …  
    661657            for (int c = 0; c < k; c++) {
    662658                int absoluteC = mk.getAbsoluteColumnIndex(c);      // This iterates over all involved columns.
    663                 MinorKey subMk = mk.getSubMinorKey(b, absoluteC);  // This is MinorKey when we omit row b and column absoluteC.
     659//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d, case 1)", om_Info.UsedBytes, "MinorKey subMk = mk.getSubMinorKey(b, absoluteC);", k);
    664660                if (!isEntryZero(b, absoluteC)) { // Only then do we have to consider this sub-determinante.
    665661                    PolyMinorValue mv;              // for storing all intermediate minors
     662                    MinorKey subMk = mk.getSubMinorKey(b, absoluteC);  // This is mk with row b and column absoluteC omitted.
     663//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d, case 1)", om_Info.UsedBytes, "PolyMinorValue mv;", k);
    666664                    if (cch.hasKey(subMk)) { // trying to find the result in the cache
    667665                        mv = cch.getValue(subMk);
    … …  
    669667                        cch.put(subMk, mv); // We need to do this with "put", as the (altered) number of retrievals may have
    670668                                            // an impact on the internal ordering among cache entries.
     669//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d, case 1)", om_Info.UsedBytes, "cch.put(subMk, mv);", k);
     670                    }
     671                    else {
     672//omUpdateInfo(); printf("\nused bytes: %12ld, before: %s  (k = %d, case 1)", om_Info.UsedBytes, "mv = getMinorPrivate(k - 1, subMk, multipleMinors, cch);", k);
     673                        mv = getMinorPrivate(k - 1, subMk, multipleMinors, cch); // recursive call
     674//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d, case 1)", om_Info.UsedBytes, "mv = getMinorPrivate(k - 1, subMk, multipleMinors, cch);", k);
     675                        // As this minor was not in the cache, we count the additions and
     676                        // multiplications that we needed to do in the recursive call:
     677                        m += mv.getMultiplications();
     678                        s += mv.getAdditions();
     679                    }
     680                    // In any case, we count all nested operations in the accumulative counters:
     681                    am += mv.getAccumulatedMultiplications();
     682                    as += mv.getAccumulatedAdditions();
     683                    pDelete(&signPoly);
     684//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d, case 1)", om_Info.UsedBytes, "pDelete(&signPoly);", k);
     685                    signPoly = pISet(sign);
     686//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d, case 1)", om_Info.UsedBytes, "signPoly = pISet(sign);", k);
     687//printf("\nmv.getResult() = %s", pString(mv.getResult()));
     688                    poly temp = pp_Mult_qq(mv.getResult(), _polyMatrix[b][absoluteC], currRing);
     689                    temp = p_Mult_q(signPoly, temp, currRing);
     690                    result = p_Add_q(result, temp, currRing);
     691//printf("\nresult = %s", pString(result));
     692//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d, case 1)", om_Info.UsedBytes, "ops(result, signPoly, mv.getResult(), _polyMatrix[b][absoluteC]);", k);
     693                    signPoly = NULL;
     694                    s++; m++; as++; am++; // This is for the addition and multiplication in the previous line of code.
     695                }
     696                sign = - sign; // alternating the sign
     697            }
     698        }
     699        else {
     700            b = - b - 1;
     701            // This means that the best line is the column with absolute (0-based) index b.
     702            // Using Laplace, the sign of the contributing minors must be iterating;
     703            // the initial sign depends on the relative index of b in minorColumnKey:
     704            int sign = (mk.getRelativeColumnIndex(b) % 2 == 0 ? 1 : -1);
     705            poly signPoly = NULL;
     706//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d, case 2)", om_Info.UsedBytes, "poly signPoly = NULL;", k);
     707            for (int r = 0; r < k; r++) {
     708                int absoluteR = mk.getAbsoluteRowIndex(r);        // This iterates over all involved rows.
     709//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d, case 2)", om_Info.UsedBytes, "MinorKey subMk = mk.getSubMinorKey(absoluteR, b);", k);
     710                if (!isEntryZero(absoluteR, b)) { // Only then do we have to consider this sub-determinante.
     711                    PolyMinorValue mv;              // for storing all intermediate minors
     712                    MinorKey subMk = mk.getSubMinorKey(absoluteR, b); // This is mk with row absoluteR and column b omitted.
     713//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d, case 2)", om_Info.UsedBytes, "PolyMinorValue mv;", k);
     714                    if (cch.hasKey(subMk)) { // trying to find the result in the cache
     715                        mv = cch.getValue(subMk);
     716                        mv.incrementRetrievals(); // once more, we made use of the cached value for key mk
     717                        cch.put(subMk, mv); // We need to do this with "put", as the (altered) number of retrievals may have
     718                                            // an impact on the internal ordering among cache entries.
     719//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d, case 2)", om_Info.UsedBytes, "cch.put(subMk, mv);", k);
    671720                    }
    672721                    else {
    … …  
    681730                    as += mv.getAccumulatedAdditions();
    682731                    pDelete(&signPoly);
     732//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d, case 2)", om_Info.UsedBytes, "pDelete(&signPoly);", k);
    683733                    signPoly = pISet(sign);
    684                     ops(result, signPoly, mv.getResult(), _polyMatrix[b][absoluteC]); // adding in "result" the product of sign,
    685                                                                                       // sub-determinante, and matrix entry
    686                     signPoly = NULL;
    687                     s++; m++; as++; am++; // This is for the addition and multiplication in the previous line of code.
    688                 }
    689                 sign = - sign; // alternating the sign
    690             }
    691         }
    692         else {
    693             b = - b - 1;
    694             // This means that the best line is the column with absolute (0-based) index b.
    695             // Using Laplace, the sign of the contributing minors must be iterating;
    696             // the initial sign depends on the relative index of b in minorColumnKey:
    697             int sign = (mk.getRelativeColumnIndex(b) % 2 == 0 ? 1 : -1);
    698             poly signPoly = NULL;
    699             for (int r = 0; r < k; r++) {
    700                 int absoluteR = mk.getAbsoluteRowIndex(r);        // This iterates over all involved rows.
    701                 MinorKey subMk = mk.getSubMinorKey(absoluteR, b); // This is MinorKey when we omit row absoluteR and column b.
    702                 if (!isEntryZero(absoluteR, b)) { // Only then do we have to consider this sub-determinante.
    703                     PolyMinorValue mv;              // for storing all intermediate minors
    704                     if (cch.hasKey(subMk)) { // trying to find the result in the cache
    705                         mv = cch.getValue(subMk);
    706                         mv.incrementRetrievals(); // once more, we made use of the cached value for key mk
    707                         cch.put(subMk, mv); // We need to do this with "put", as the (altered) number of retrievals may have
    708                                             // an impact on the internal ordering among cache entries.
    709                     }
    710                     else {
    711                         mv = getMinorPrivate(k - 1, subMk, multipleMinors, cch); // recursive call
    712                         // As this minor was not in the cache, we count the additions and
    713                         // multiplications that we needed to do in the recursive call:
    714                         m += mv.getMultiplications();
    715                         s += mv.getAdditions();
    716                     }
    717                     // In any case, we count all nested operations in the accumulative counters:
    718                     am += mv.getAccumulatedMultiplications();
    719                     as += mv.getAccumulatedAdditions();
    720                     pDelete(&signPoly);
    721                     signPoly = pISet(sign);
    722                     ops(result, signPoly, mv.getResult(), _polyMatrix[absoluteR][b]); // adding in "result" the product of sign,
    723                                                                                       // sub-determinante, and matrix entry
     734//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d, case 2)", om_Info.UsedBytes, "signPoly = pISet(sign);", k);
     735                    poly temp = pp_Mult_qq(mv.getResult(), _polyMatrix[absoluteR][b], currRing);
     736                    temp = p_Mult_q(signPoly, temp, currRing);
     737                    result = p_Add_q(result, temp, currRing);
     738//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d, case 2)", om_Info.UsedBytes, "ops(result, signPoly, mv.getResult(), _polyMatrix[absoluteR][b]);", k);
    724739                    signPoly = NULL;
    725740                    s++; m++; as++; am++; // This is for the addition and multiplication in the previous line of code.
    … …  
    734749        if (as < 0) as = 0; // may happen when all subminors are zero and no addition needs to be performed
    735750        PolyMinorValue newMV(result, m, s, am, as, 1, potentialRetrievals);
    736         pDelete(&result);
     751//printf("\nMINOR to put: %s", pString(result));
     752//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d)", om_Info.UsedBytes, "PolyMinorValue newMV(result, m, s, am, as, 1, potentialRetrievals);", k);
     753        pDelete(&result); result = NULL;
     754//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d)", om_Info.UsedBytes, "pDelete(&result);", k);
    737755        cch.put(mk, newMV); // Here's the actual put inside the cache.
     756//omUpdateInfo(); printf("\nused bytes: %12ld, after: %s  (k = %d)", om_Info.UsedBytes, "cch.put(mk, newMV);", k);
    738757        return newMV;
    739758    }
Note: See TracChangeset for help on using the changeset viewer.