The Original CHomP Software
Public Member Functions | Public Attributes | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
chomp::homology::mmatrix< euclidom > Class Template Reference

A class for representing sparse matrices containing elements of the 'euclidom' type. More...

#include <chains.h>

Public Member Functions

 mmatrix ()
 The default constructor. More...
 
 mmatrix (const mmatrix< euclidom > &m)
 The copy constructor. More...
 
mmatrix< euclidom > & operator= (const mmatrix< euclidom > &s)
 The assignment operator. More...
 
 ~mmatrix ()
 The destructor of a matrix. More...
 
void define (int_t numrows, int_t numcols)
 Defines the number of rows and columns and increases the internal tables if necessary. More...
 
void identity (int_t size)
 Defines the matrix to be the identity of the given size. More...
 
void add (int_t row, int_t col, const euclidom &e)
 Adds a value to the given element of the matrix. More...
 
euclidom get (int_t row, int_t col) const
 Returns the value at the desired location of the matrix. More...
 
const chain< euclidom > & getrow (int_t n) const
 Returns a reference to the entire row stored as a chain. More...
 
const chain< euclidom > & getcol (int_t n) const
 Returns a reference to the entire column stored as a chain. More...
 
int_t getnrows () const
 Returns the number of rows in the matrix. More...
 
int_t getncols () const
 Returns the number of columns in the matrix. More...
 
void addrow (int_t dest, int_t source, const euclidom &e)
 Adds one row to another with a given coefficient. More...
 
void addcol (int_t dest, int_t source, const euclidom &e)
 Adds one column to another with a given coefficient. More...
 
void swaprows (int_t i, int_t j)
 Swaps two rows of the matrix. More...
 
void swapcols (int_t i, int_t j)
 Swaps two columns of the matrix. More...
 
void multiplyrow (int_t n, const euclidom &e)
 Multiplies the row by the given coefficient and updates columns. More...
 
void multiplycol (int_t n, const euclidom &e)
 Multiplies the column by the given coefficient and updates rows. More...
 
int_t findrow (int_t req_elements=1, int_t start=-1) const
 Finds a row containing at least the required number of nonzero elements, starting at the given row. More...
 
int_t findcol (int_t req_elements=1, int_t start=-1) const
 Finds a column containing at least the required number of nonzero elements, starting at the given column. More...
 
int_t reducerow (int_t n, int_t preferred)
 Reduces the given row of the matrix and updates its columns. More...
 
int_t reducecol (int_t n, int_t preferred)
 Reduces the given column of the matrix and updates its rows. More...
 
void simple_reductions (bool quiet=false)
 Runs some random simple reductions. More...
 
void simple_form (bool quiet=false)
 Transforms the matrix to a simple form (nearly SNF). More...
 
int_t arrange_towards_SNF (int_t *invertible_count=0)
 Swaps rows and columns to make the simple form closer to SNF. More...
 
void simple_form_to_SNF (bool quiet=false)
 Transforms the matrix from the simple form to actual SNF. More...
 
void invert (void)
 Inverts the matrix. Throws an error message on failure. More...
 
void multiply (const mmatrix< euclidom > &m1, const mmatrix< euclidom > &m2)
 Computes the product of the two given matrices. More...
 
void submatrix (const mmatrix< euclidom > &matr, const chain< euclidom > &domain, const chain< euclidom > &range)
 Extracts a submatrix from the given matrix. More...
 
outputstream & show_hom_col (outputstream &out, int_t col, const chain< euclidom > &range, const char *txt=NULL) const
 Writes a column with only these coefficients which exist in 'range', and shows their positions in that chain. More...
 
std::ostream & show_hom_col (std::ostream &out, int_t col, const chain< euclidom > &range, const char *txt=NULL) const
 Writes a column with only these coefficients which exist in 'range', and shows their positions in that chain. More...
 
outputstream & showrowscols (outputstream &out, chain< euclidom > *table, int_t tablen, int_t first=0, int_t howmany=0, const char *label=NULL) const
 Writes the matrix to an output stream by its rows or columns. More...
 
outputstream & showrows (outputstream &out, int_t first=0, int_t howmany=0, const char *label="Row ") const
 Writes the matrix to an output stream by its rows. More...
 
std::ostream & showrows (std::ostream &out, int_t first=0, int_t howmany=0, const char *label="Row ") const
 Writes the matrix to an output stream by its rows. More...
 
outputstream & showcols (outputstream &out, int_t first=0, int_t howmany=0, const char *label="Col ") const
 Writes the matrix to an output stream by its rows. More...
 
std::ostream & showcols (std::ostream &out, int_t first=0, int_t howmany=0, const char *label="Col ") const
 Writes the matrix to an output stream by its rows. More...
 
outputstream & showmap (outputstream &out, const char *maplabel=NULL, const char *xlabel=NULL, const char *ylabel=NULL) const
 Writes the matrix as a linear map on generators. More...
 
std::ostream & showmap (std::ostream &out, const char *maplabel=NULL, const char *xlabel=NULL, const char *ylabel=NULL) const
 Writes the matrix as a linear map on generators. More...
 

Public Attributes

simplelist< mmatrix< euclidom > > dom_dom
 This is a list of matrices to be updated together with the changes to the columns or rows of the current matrix. More...
 
simplelist< mmatrix< euclidom > > dom_img
 
simplelist< mmatrix< euclidom > > img_dom
 
simplelist< mmatrix< euclidom > > img_img
 

Private Member Functions

int_t findrowcol (int_t req_elements, int_t start, int which) const
 An internal procedure for both findrow and findcol. More...
 
void increase (int_t numrows, int_t numcols)
 Increases tables to be enough to keep the given number of columns and rows. More...
 
void increaserows (int_t numrows)
 Increases tables to be enough to keep the given number of rows. More...
 
void increasecols (int_t numcols)
 Increases tables to be enough to keep the given number of columns. More...
 
void division_SNF_correction (const euclidom &a, int_t pos1, const euclidom &b, int_t pos2)
 Makes a correction of division in the "diagonal" at the given two positions, so that the entry at pos1 divides the one at pos2. More...
 
void mult_left (const int_t setRows[], const int_t setCols[], const mmatrix< euclidom > &M, const mmatrix< euclidom > &invM, bool update_linked)
 Multiplies the matrix from the left by an invertible square matrix whose possibly nonzero entries are only in the given rows and columns. More...
 
void mult_right (const int_t setRows[], const int_t setCols[], const mmatrix< euclidom > &M, const mmatrix< euclidom > &invM, bool update_linked)
 Multiplies the matrix from the right by an invertible square matrix whose possibly nonzero entries are only in the given rows and columns. More...
 

Static Private Member Functions

static void extendedGCD (const euclidom &a, const euclidom &b, euclidom &x, euclidom &y)
 Extended Euclidean algorithm for the computation of the greatest common divisor, together with the coefficients that satisfy the Bezout's identity ax + by = gcd (a,b). More...
 

Private Attributes

int_t nrows
 The number of rows in the matrix. More...
 
int_t ncols
 The number of columns in the matrix. More...
 
int_t allrows
 The number of allocated rows. More...
 
int_t allcols
 The number of allocated columns. More...
 
chain< euclidom > * rows
 The rows of the matrix. More...
 
chain< euclidom > * cols
 The columns of the matrix. More...
 

Detailed Description

template<class euclidom>
class chomp::homology::mmatrix< euclidom >

A class for representing sparse matrices containing elements of the 'euclidom' type.

This class has very specific functionality to be used mainly for the purpose of homology computation.

Definition at line 1066 of file chains.h.

Constructor & Destructor Documentation

◆ mmatrix() [1/2]

template<class euclidom >
chomp::homology::mmatrix< euclidom >::mmatrix
inline

The default constructor.

Definition at line 1347 of file chains.h.

1347 : nrows (0), ncols (0),
1348 allrows (0), allcols (0), rows (NULL), cols (NULL)
1349{
1350 return;
1351} /* mmatrix<euclidom>::mmatrix */
chomp::homology::mmatrix::allrows
int_t allrows
The number of allocated rows.
Definition: chains.h:1268
chomp::homology::mmatrix::nrows
int_t nrows
The number of rows in the matrix.
Definition: chains.h:1262
chomp::homology::mmatrix::rows
chain< euclidom > * rows
The rows of the matrix.
Definition: chains.h:1274
chomp::homology::mmatrix::allcols
int_t allcols
The number of allocated columns.
Definition: chains.h:1271
chomp::homology::mmatrix::ncols
int_t ncols
The number of columns in the matrix.
Definition: chains.h:1265
chomp::homology::mmatrix::cols
chain< euclidom > * cols
The columns of the matrix.
Definition: chains.h:1277

◆ mmatrix() [2/2]

template<class euclidom >
chomp::homology::mmatrix< euclidom >::mmatrix ( const mmatrix< euclidom > &  m)
inline

The copy constructor.

Added by Marcin Zelawski and fixed by Pawel Pilarczyk.

Definition at line 1381 of file chains.h.

1382{
1383 nrows = m.nrows;
1384 ncols = m.ncols;
1385 allrows = m.allrows;
1386 allcols = m.allcols;
1387
1388 rows = NULL;
1389 cols = NULL;
1390 if (m. allrows > 0)
1391 {
1392 chain<euclidom> *newrows = new chain<euclidom> [m. allrows];
1393 if (!newrows)
1394 throw "Not enough memory for matrix rows.";
1395 for (int_t i = 0; i < m. allrows; ++ i)
1396 newrows [i] = m. rows [i];
1397 rows = newrows;
1398 }
1399
1400 if (m. allcols > 0)
1401 {
1402 chain<euclidom> *newcols = new chain<euclidom> [m. allcols];
1403 if (!newcols)
1404 throw "Not enough memory for matrix columns.";
1405 for (int_t i = 0; i < m.allcols; ++ i)
1406 newcols [i] = m. cols [i];
1407 cols = newcols;
1408 }
1409} /* mmatrix<euclidom>::mmatrix */
int_t
int int_t
Index type for indexing arrays, counting cubes, etc.
Definition: config.h:115

References chomp::homology::mmatrix< euclidom >::allcols, chomp::homology::mmatrix< euclidom >::allrows, chomp::homology::mmatrix< euclidom >::ncols, and chomp::homology::mmatrix< euclidom >::nrows.

◆ ~mmatrix()

template<class euclidom >
chomp::homology::mmatrix< euclidom >::~mmatrix
inline

The destructor of a matrix.

Definition at line 1354 of file chains.h.

1355{
1356 if (rows)
1357 delete [] rows;
1358 if (cols)
1359 delete [] cols;
1360 return;
1361} /* mmatrix<euclidom>::~mmatrix */

Member Function Documentation

◆ add()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::add ( int_t  row,
int_t  col,
const euclidom &  e 
)
inline

Adds a value to the given element of the matrix.

Definition at line 1468 of file chains.h.

1470{
1471 if (row < 0)
1472 throw "Incorrect row number.";
1473 if (col < 0)
1474 throw "Incorrect column number.";
1475 if (row >= nrows)
1476 {
1477 if (row >= allrows)
1478 increaserows (row + row / 2 + 1);
1479 nrows = row + 1;
1480 }
1481 if (col >= ncols)
1482 {
1483 if (col >= allcols)
1484 increasecols (col + col / 2 + 1);
1485 ncols = col + 1;
1486 }
1487 if (e == 0)
1488 return;
1489 cols [col]. add (row, e);
1490 rows [row]. add (col, e);
1491 return;
1492} /* mmatrix<euclidom>::add */
chomp::homology::mmatrix::increaserows
void increaserows(int_t numrows)
Increases tables to be enough to keep the given number of rows.
Definition: chains.h:2606
chomp::homology::mmatrix::increasecols
void increasecols(int_t numcols)
Increases tables to be enough to keep the given number of columns.
Definition: chains.h:2623
chomp::homology::mmatrix::add
void add(int_t row, int_t col, const euclidom &e)
Adds a value to the given element of the matrix.
Definition: chains.h:1468

◆ addcol()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::addcol ( int_t  dest,
int_t  source,
const euclidom &  e 
)
inline

Adds one column to another with a given coefficient.

Updates all the matrices which are linked to this one.

Definition at line 1572 of file chains.h.

1574{
1575 // check if the parameters are not out of range
1576 if ((dest < 0) || (dest >= ncols) || (source < 0) ||
1577 (source >= ncols))
1578 throw "Trying to add columns out of range.";
1579
1580 // add this column
1581 cols [dest]. add (cols [source], e, dest, rows);
1582
1583 // update the other matrices
1584 mmatrix<euclidom> *m;
1585 while ((m = dom_dom. take ()) != NULL)
1586 if (m -> cols)
1587 m -> cols [dest]. add (m -> cols [source], e,
1588 dest, m -> rows);
1589
1590 while ((m = dom_img. take ()) != NULL)
1591 if (m -> rows)
1592 m -> rows [source]. add (m -> rows [dest], -e,
1593 source, m -> cols);
1594
1595 return;
1596} /* mmatrix<euclidom>::addcol */
chomp::homology::mmatrix::dom_img
simplelist< mmatrix< euclidom > > dom_img
Definition: chains.h:1205
chomp::homology::mmatrix::dom_dom
simplelist< mmatrix< euclidom > > dom_dom
This is a list of matrices to be updated together with the changes to the columns or rows of the curr...
Definition: chains.h:1205

◆ addrow()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::addrow ( int_t  dest,
int_t  source,
const euclidom &  e 
)
inline

Adds one row to another with a given coefficient.

Updates all the matrices which are linked to this one.

Definition at line 1545 of file chains.h.

1547{
1548 // check if the parameters are not out of range
1549 if ((dest < 0) || (dest >= nrows) || (source < 0) ||
1550 (source >= nrows))
1551 throw "Trying to add rows out of range.";
1552
1553 // add this row
1554 rows [dest]. add (rows [source], e, dest, cols);
1555
1556 // update the other matrices
1557 mmatrix<euclidom> *m;
1558 while ((m = img_img. take ()) != NULL)
1559 if (m -> rows)
1560 m -> rows [dest]. add (m -> rows [source], e,
1561 dest, m -> cols);
1562
1563 while ((m = img_dom. take ()) != NULL)
1564 if (m -> cols)
1565 m -> cols [source]. add (m -> cols [dest], -e,
1566 source, m -> rows);
1567
1568 return;
1569} /* mmatrix<euclidom>::addrow */
chomp::homology::mmatrix::img_img
simplelist< mmatrix< euclidom > > img_img
Definition: chains.h:1206
chomp::homology::mmatrix::img_dom
simplelist< mmatrix< euclidom > > img_dom
Definition: chains.h:1205

◆ arrange_towards_SNF()

template<class euclidom >
int_t chomp::homology::mmatrix< euclidom >::arrange_towards_SNF ( int_t *  invertible_count = 0)
inline

Swaps rows and columns to make the simple form closer to SNF.

After these changes, all the invertible coefficients are gathered at the beginning of the "diagonal" and are made equal 1, and the noninvertible coefficients are moved to follow them along the "diagonal". Updates all the matrices which are linked to this one. If given a nonzero pointer, saves the number of invertible entries at the "diagonal". Returns the number of nonzero entries at the "diagonal". WARNING: SEEMS NOT TO WORK CORRECTLY AT THE MOMENT.

Definition at line 2062 of file chains.h.

2063{
2064 // prepare a counter for nonzero entries of the diagonal
2065 int_t cur = 0;
2066
2067 // move all the invertible nonzero entries to the front
2068 for (int_t n = 0; n < ncols; ++ n)
2069 {
2070 if (cols [n]. empty ())
2071 continue;
2072 if (cols [n]. coef (0). delta () != 1)
2073 continue;
2074 int_t r = cols [n]. num (0);
2075 if (n != cur)
2076 swapcols (n, cur);
2077 if (r != cur)
2078 swaprows (r, cur);
2079 ++ cur;
2080 }
2081
2082 // store the number of invertible entries at the diagonal
2083 if (invertible_count)
2084 *invertible_count = cur;
2085
2086 // move all the remaining nonzero entries to the front
2087 for (int_t n = cur; n < ncols; ++ n)
2088 {
2089 if (cols [n]. empty ())
2090 continue;
2091 int_t r = cols [n]. num (0);
2092 if (n != cur)
2093 swapcols (n, cur);
2094 if (r != cur)
2095 swaprows (r, cur);
2096 ++ cur;
2097 }
2098
2099 return cur;
2100} /* mmatrix<euclidom>::arrange_towards_SNF */
chomp::homology::mmatrix::swapcols
void swapcols(int_t i, int_t j)
Swaps two columns of the matrix.
Definition: chains.h:1626
chomp::homology::mmatrix::swaprows
void swaprows(int_t i, int_t j)
Swaps two rows of the matrix.
Definition: chains.h:1599

◆ define()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::define ( int_t  numrows,
int_t  numcols 
)
inline

Defines the number of rows and columns and increases the internal tables if necessary.

Useful for creating large zero matrices.

Definition at line 1364 of file chains.h.

1365{
1366 // verify that no nonzero entry will be thrown away
1367 if ((nrows > numrows) || (ncols > numcols))
1368 throw "Trying to define a matrix smaller than it really is";
1369
1370 // increase the size of the matrix to fit the defined one
1371 increase (numrows, numcols);
1372
1373 // set the number of rows and the number of columns as requested
1374 nrows = numrows;
1375 ncols = numcols;
1376
1377 return;
1378} /* mmatrix<euclidom>::define */
chomp::homology::mmatrix::increase
void increase(int_t numrows, int_t numcols)
Increases tables to be enough to keep the given number of columns and rows.
Definition: chains.h:2598

◆ division_SNF_correction()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::division_SNF_correction ( const euclidom &  a,
int_t  pos1,
const euclidom &  b,
int_t  pos2 
)
inlineprivate

Makes a correction of division in the "diagonal" at the given two positions, so that the entry at pos1 divides the one at pos2.

Note that pos1 must be smaller than pos2. This procedure is based upon the suggestions at http://en.wikipedia.org/wiki/Smith_normal_form. Updates all the matrices which are linked to this one.

Definition at line 2144 of file chains.h.

2146{
2147// sout << "=== DEBUG: division_SNF_correction. ===\n";
2148// sout << "DEBUG: Initial matrix:\n" << *this;
2149
2150 // compute the GCD and the Bezout's identity coefficients
2151 euclidom sigma;
2152 euclidom tau;
2153 extendedGCD (a, b, sigma, tau);
2154 euclidom beta (a * sigma + b * tau);
2155 euclidom alpha (a / beta);
2156 euclidom gamma (b / beta);
2157// sout << "DEBUG: a = " << a << ", b = " << b << ", beta = " << beta <<
2158// " = " << a << "*" << sigma << "+" << b << "*" << tau <<
2159// ", a/beta = " << alpha << ", b/beta = " << gamma <<
2160// ".\nsigma = " << sigma << ", tau = " << tau <<
2161// ", alpha = " << alpha << ", gamma = " << gamma << ".\n";
2162
2163 // add the second column to the first
2164 euclidom one;
2165 one = 1;
2166 this -> addcol (pos1, pos2, one);
2167
2168 // multiply the selected columns/rows by a special 2x2 matrix:
2169 // prepare a chain that defines the columns and rows to be affected
2170 int_t setRowsCols [2];
2171 setRowsCols [0] = pos1;
2172 setRowsCols [1] = pos2;
2173
2174 // prepare a matrix to multiply from the left
2175 mmatrix<euclidom> M;
2176 M. define (2, 2);
2177 M. add (0, 0, sigma);
2178 M. add (0, 1, tau);
2179 M. add (1, 0, -gamma);
2180 M. add (1, 1, alpha);
2181// sout << "DEBUG: Matrix M:\n" << M;
2182
2183 // prepare the inverse of this matrix
2184 mmatrix<euclidom> invM;
2185 invM. define (2, 2);
2186 invM. add (0, 0, alpha);
2187 invM. add (0, 1, -tau);
2188 invM. add (1, 0, gamma);
2189 invM. add (1, 1, sigma);
2190// sout << "DEBUG: Inverse of the matrix M:\n" << invM;
2191
2192 // multiply the current matrix from the left by the special matrix
2193 this -> mult_left (setRowsCols, setRowsCols, M, invM, true);
2194
2195 // add the first column to the second one with a special coefficient
2196 // to make this part of the matirx diagonal again
2197 this -> addcol (pos2, pos1, (-tau) * gamma);
2198
2199// sout << "DEBUG: Final matrix:\n" << *this;
2200 return;
2201} /* mmatrix<euclidom>::division_SNF_correction */
chomp::homology::mmatrix::define
void define(int_t numrows, int_t numcols)
Defines the number of rows and columns and increases the internal tables if necessary.
Definition: chains.h:1364
chomp::homology::mmatrix::addcol
void addcol(int_t dest, int_t source, const euclidom &e)
Adds one column to another with a given coefficient.
Definition: chains.h:1572
chomp::homology::mmatrix::extendedGCD
static void extendedGCD(const euclidom &a, const euclidom &b, euclidom &x, euclidom &y)
Extended Euclidean algorithm for the computation of the greatest common divisor, together with the co...
Definition: chains.h:2401
chomp::homology::mmatrix::mult_left
void mult_left(const int_t setRows[], const int_t setCols[], const mmatrix< euclidom > &M, const mmatrix< euclidom > &invM, bool update_linked)
Multiplies the matrix from the left by an invertible square matrix whose possibly nonzero entries are...
Definition: chains.h:2205

◆ extendedGCD()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::extendedGCD ( const euclidom &  a,
const euclidom &  b,
euclidom &  x,
euclidom &  y 
)
inlinestaticprivate

Extended Euclidean algorithm for the computation of the greatest common divisor, together with the coefficients that satisfy the Bezout's identity ax + by = gcd (a,b).

Based upon http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm (section "Formal description of the algorithm", subsection "Iterative method").

Definition at line 2400 of file chains.h.

2402{
2403 euclidom aa (a), bb (b);
2404 euclidom xx, yy, lastx, lasty;
2405 xx = 0;
2406 yy = 1;
2407 lastx = 1;
2408 lasty = 0;
2409 while (!(bb == 0))
2410 {
2411 euclidom quotient (aa / bb);
2412 euclidom remainder (aa % bb);
2413 aa = bb;
2414 bb = remainder;
2415 euclidom xxx = lastx - quotient * xx;
2416 lastx = xx;
2417 xx = xxx;
2418 euclidom yyy = lasty - quotient * yy;
2419 lasty = yy;
2420 yy = yyy;
2421 }
2422 x = lastx;
2423 y = lasty;
2424 return;
2425} /* mmatrix<euclidom>::extendedGCD */

◆ findcol()

template<class euclidom >
int_t chomp::homology::mmatrix< euclidom >::findcol ( int_t  req_elements = 1,
int_t  start = -1 
) const
inline

Finds a column containing at least the required number of nonzero elements, starting at the given column.

If 'req_elements' is set to -1 then looks for a zero column. Returns the number of the column satisfying the desired property, or -1 if not found.

Definition at line 1759 of file chains.h.

1760{
1761 return findrowcol (req_elements, start, 0);
1762} /* mmatrix<euclidom>::findcol */
chomp::homology::mmatrix::findrowcol
int_t findrowcol(int_t req_elements, int_t start, int which) const
An internal procedure for both findrow and findcol.
Definition: chains.h:1685

◆ findrow()

template<class euclidom >
int_t chomp::homology::mmatrix< euclidom >::findrow ( int_t  req_elements = 1,
int_t  start = -1 
) const
inline

Finds a row containing at least the required number of nonzero elements, starting at the given row.

If 'req_elements' is set to -1 then looks for a zero row. Returns the number of the row satisfying the desired property, or -1 if not found.

Definition at line 1753 of file chains.h.

1754{
1755 return findrowcol (req_elements, start, 1);
1756} /* mmatrix<euclidom>::findrow */

◆ findrowcol()

template<class euclidom >
int_t chomp::homology::mmatrix< euclidom >::findrowcol ( int_t  req_elements,
int_t  start,
int  which 
) const
inlineprivate

An internal procedure for both findrow and findcol.

The value of which is: row = 1, col = 0.

Definition at line 1685 of file chains.h.

1687{
1688 // start at the starting point
1689 int_t i = start;
1690 int_t random_i = -1;
1691
1692 // set loop to none
1693 int_t loopcounter = 0;
1694
1695 // if a random start is requested, initialize it and set loop to 1
1696 if (start < 0)
1697 {
1698 i = random_i = std::rand () % (which ? nrows : ncols);
1699 loopcounter = 1;
1700 }
1701
1702 // select some candidates
1703 int_t candidate = -1;
1704 int_t candidates_left = 3;
1705
1706 // if the table has one of its dimensions trivial, return the result
1707 if (which ? !ncols : !nrows)
1708 return (((req_elements > 0) ||
1709 (i >= (which ? nrows : ncols))) ? -1 : i);
1710
1711 // while the current position has not gone beyond the table
1712 while (i < (which ? nrows : ncols))
1713 {
1714 // if there is an appropriate row/column, return its number
1715 int_t l = (which ? rows : cols) [i]. size ();
1716 if ((req_elements >= 0) && (l >= req_elements))
1717 return i;
1718 else if ((req_elements < 0) && !l)
1719 {
1720 if (!candidates_left || !(which ? rows : cols) [i].
1721 contains_non_invertible ())
1722 return i;
1723 else
1724 {
1725 candidate = i;
1726 -- candidates_left;
1727 if (start < 0)
1728 {
1729 random_i = std::rand () %
1730 (which ? nrows : ncols);
1731 i = random_i - 1;
1732 loopcounter = 1;
1733 }
1734 }
1735 }
1736
1737 // otherwise increase the counter and rewind to 0 if needed
1738 if (++ i >= (which ? nrows : ncols))
1739 if (loopcounter --)
1740 i = 0;
1741
1742 // if the searching was started at a random position,
1743 // finish earlier
1744 if ((random_i >= 0) && !loopcounter && (i >= random_i))
1745 break;
1746 }
1747
1748 // if not found, return the recent candidate (or -1 if none)
1749 return candidate;
1750} /* mmatrix<euclidom>::findrowcol */

◆ get()

template<class euclidom >
euclidom chomp::homology::mmatrix< euclidom >::get ( int_t  row,
int_t  col 
) const
inline

Returns the value at the desired location of the matrix.

If 'row' or 'col' is set to -1, gets the first element in it or returns 0 if the colum/row is empty.

Definition at line 1495 of file chains.h.

1497{
1498 if ((row >= nrows) || (col >= ncols))
1499 {
1500 euclidom zero;
1501 zero = 0;
1502 return zero;
1503 }
1504 if (row >= 0)
1505 return rows [row]. getcoefficient (col);
1506 else if (col >= 0)
1507 return cols [col]. getcoefficient (row);
1508 else
1509 {
1510 euclidom zero;
1511 zero = 0;
1512 return zero;
1513 }
1514} /* mmatrix<euclidom>::get */

◆ getcol()

template<class euclidom >
const chain< euclidom > & chomp::homology::mmatrix< euclidom >::getcol ( int_t  n) const
inline

Returns a reference to the entire column stored as a chain.

Definition at line 1525 of file chains.h.

1526{
1527 if ((n < 0) || (n >= ncols))
1528 throw "Incorrect column number.";
1529 return cols [n];
1530} /* mmatrix<euclidom>::getcol */

◆ getncols()

template<class euclidom >
int_t chomp::homology::mmatrix< euclidom >::getncols
inline

Returns the number of columns in the matrix.

Definition at line 1539 of file chains.h.

1540{
1541 return ncols;
1542} /* mmatrix<euclidom>::getncols */

◆ getnrows()

template<class euclidom >
int_t chomp::homology::mmatrix< euclidom >::getnrows
inline

Returns the number of rows in the matrix.

Definition at line 1533 of file chains.h.

1534{
1535 return nrows;
1536} /* mmatrix<euclidom>::getnrows */

◆ getrow()

template<class euclidom >
const chain< euclidom > & chomp::homology::mmatrix< euclidom >::getrow ( int_t  n) const
inline

Returns a reference to the entire row stored as a chain.

Definition at line 1517 of file chains.h.

1518{
1519 if ((n < 0) || (n >= nrows))
1520 throw "Incorrect row number.";
1521 return rows [n];
1522} /* mmatrix<euclidom>::getrow */

◆ identity()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::identity ( int_t  size)
inline

Defines the matrix to be the identity of the given size.

Definition at line 1452 of file chains.h.

1453{
1454 if (!nrows && !ncols)
1455 increase (size, size);
1456 else if ((size > nrows) || (size > ncols))
1457 size = (nrows < ncols) ? nrows : ncols;
1458 for (int_t i = 0; i < size; ++ i)
1459 {
1460 euclidom one;
1461 one = 1;
1462 add (i, i, one);
1463 }
1464 return;
1465} /* mmatrix<euclidom>::identity */

◆ increase()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::increase ( int_t  numrows,
int_t  numcols 
)
inlineprivate

Increases tables to be enough to keep the given number of columns and rows.

This function does not set 'nrows' and 'ncols'.

Definition at line 2598 of file chains.h.

2599{
2600 increaserows (numrows);
2601 increasecols (numcols);
2602 return;
2603} /* mmatrix<euclidom>::increase */

◆ increasecols()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::increasecols ( int_t  numcols)
inlineprivate

Increases tables to be enough to keep the given number of columns.

Definition at line 2623 of file chains.h.

2624{
2625 if (allcols >= numcols)
2626 return;
2627 chain<euclidom> *newcols = new chain<euclidom> [numcols];
2628 if (!newcols)
2629 throw "Not enough memory for matrix columns.";
2630 for (int_t i = 0; i < ncols; ++ i)
2631 newcols [i]. take (cols [i]);
2632 if (cols)
2633 delete [] cols;
2634 cols = newcols;
2635 allcols = numcols;
2636
2637 return;
2638} /* mmatrix<euclidom>::increasecols */

◆ increaserows()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::increaserows ( int_t  numrows)
inlineprivate

Increases tables to be enough to keep the given number of rows.

Definition at line 2606 of file chains.h.

2607{
2608 if (allrows >= numrows)
2609 return;
2610 chain<euclidom> *newrows = new chain<euclidom> [numrows];
2611 if (!newrows)
2612 throw "Not enough memory for matrix rows.";
2613 for (int_t i = 0; i < nrows; ++ i)
2614 newrows [i]. take (rows [i]);
2615 if (rows)
2616 delete [] rows;
2617 rows = newrows;
2618 allrows = numrows;
2619 return;
2620} /* mmatrix<euclidom>::increaserows */

◆ invert()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::invert ( void  )
inline

Inverts the matrix. Throws an error message on failure.

Definition at line 2428 of file chains.h.

2429{
2430 // check if the matrix is square
2431 if (nrows != ncols)
2432 throw "Trying to invert a non-square matrix.";
2433
2434 // if the matrix is trivial, nothing needs to be done
2435 if (!nrows)
2436 return;
2437
2438 // create the identity matrix of the appropriate size
2439 mmatrix<euclidom> m;
2440 m. identity (ncols);
2441
2442 // transform the matrix to the identity
2443 // by row operations (swapping and adding)
2444 // and apply the same operations to the matrix 'm'
2445 for (int_t col = 0; col < ncols; ++ col)
2446 {
2447 // find an invertible element in the column
2448 int_t len = cols [col]. size ();
2449 if (len <= 0)
2450 {
2451 throw "Matrix inverting: Zero column found.";
2452 }
2453 int_t chosen = 0;
2454 while ((chosen < len) &&
2455 ((cols [col]. num (chosen) < col) ||
2456 (cols [col]. coef (chosen). delta () != 1)))
2457 {
2458 ++ chosen;
2459 }
2460 if (chosen >= len)
2461 {
2462 throw "Matrix inverting: "
2463 "No invertible element in a column.";
2464 }
2465
2466 // make the leading entry equal 1 in the chosen row
2467 euclidom invcoef;
2468 invcoef = 1;
2469 invcoef = invcoef / cols [col]. coef (chosen);
2470 m. multiplyrow (cols [col]. num (chosen), invcoef);
2471 multiplyrow (cols [col]. num (chosen), invcoef);
2472
2473 // move the chosen row to the diagonal position
2474 m. swaprows (col, cols [col]. num (chosen));
2475 swaprows (col, cols [col]. num (chosen));
2476
2477 // zero the column below and above the chosen entry
2478 invcoef = -1;
2479 for (int_t i = 0; i < len; ++ i)
2480 {
2481 if (cols [col]. num (i) == col)
2482 continue;
2483 euclidom coef = invcoef * cols [col]. coef (i);
2484 m. addrow (cols [col]. num (i), col, coef);
2485 addrow (cols [col]. num (i), col, coef);
2486 -- i;
2487 -- len;
2488 }
2489 }
2490
2491 // take the matrix 'm' as the result
2492 for (int_t i = 0; i < ncols; ++ i)
2493 {
2494 cols [i]. take (m. cols [i]);
2495 rows [i]. take (m. rows [i]);
2496 }
2497
2498 return;
2499} /* mmatrix<euclidom>::invert */
chomp::homology::mmatrix::addrow
void addrow(int_t dest, int_t source, const euclidom &e)
Adds one row to another with a given coefficient.
Definition: chains.h:1545
chomp::homology::mmatrix::multiplyrow
void multiplyrow(int_t n, const euclidom &e)
Multiplies the row by the given coefficient and updates columns.
Definition: chains.h:1653
chomp::homology::mmatrix::identity
void identity(int_t size)
Defines the matrix to be the identity of the given size.
Definition: chains.h:1452

◆ mult_left()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::mult_left ( const int_t  setRows[],
const int_t  setCols[],
const mmatrix< euclidom > &  M,
const mmatrix< euclidom > &  invM,
bool  update_linked 
)
inlineprivate

Multiplies the matrix from the left by an invertible square matrix whose possibly nonzero entries are only in the given rows and columns.

The matrix provided for multiplication consists only of the selected rows and columns, numbered sequentially from 0. If it is known that the matrix to be multiplied has nonzero entries in the given rows only in the given columns then this information can be provided to speed up the multiplication. If requested, updates the matrices linked to this one.

Definition at line 2204 of file chains.h.

2210{
2211 euclidom zero;
2212 zero = 0;
2213 euclidom one;
2214 one = 1;
2215
2216 // compute the possibly changed rows of the matrix
2217 int_t size = M. getnrows ();
2218 auto_array<chain<euclidom> > newRows_p (new chain<euclidom> [size]);
2219 chain<euclidom> *newRows = newRows_p. get ();
2220 for (int_t row = 0; row < size; ++ row)
2221 {
2222 // determine the numbers of columns to process
2223 chain<euclidom> affected;
2224 for (int_t col = 0; col < size; ++ col)
2225 {
2226 const chain<euclidom> &rowChain =
2227 this -> getrow (setCols [col]);
2228 int_t rowSize = rowChain. size ();
2229 for (int cur = 0; cur < rowSize; ++ cur)
2230 {
2231 int_t num (rowChain. num (cur));
2232 if (affected. findnumber (num) < 0)
2233 affected. add (num, one);
2234 }
2235 }
2236
2237 // multiply these columns by the current row of M
2238 int_t col_count = affected. size ();
2239 for (int_t col = 0; col < col_count; ++ col)
2240 {
2241 int_t col_nr = affected. num (col);
2242 euclidom e;
2243 e = 0;
2244 for (int_t k = 0; k < size; ++ k)
2245 {
2246 int_t row_k = setCols [k]; // sic!
2247 e += M. get (row, k) *
2248 this -> get (row_k, col_nr);
2249 }
2250 if (!(e == 0))
2251 newRows [row]. add (col_nr, e);
2252 }
2253 }
2254
2255 // replace the previous rows in the matrix with the new ones
2256 for (int_t row = 0; row < size; ++ row)
2257 {
2258 int_t row_nr = setRows [row];
2259 const chain<euclidom> &row_ch (newRows [row]);
2260
2261 // eliminate entries that do not appear in the new row
2262 const chain<euclidom> row_prev (this -> getrow (row_nr));
2263 int_t len_prev = row_prev. size ();
2264 for (int_t i = 0; i < len_prev; ++ i)
2265 {
2266 int_t col_nr (row_prev. num (i));
2267 euclidom e (row_ch. getcoefficient (col_nr));
2268 if (e == zero)
2269 {
2270 euclidom coef (this -> get (row_nr, col_nr));
2271 this -> add (row_nr, col_nr, -coef);
2272 }
2273 }
2274
2275 // set the other entries to the ones in the new row
2276 int_t len = row_ch. size ();
2277 for (int_t i = 0; i < len; ++ i)
2278 {
2279 int_t col_nr (row_ch. num (i));
2280 euclidom e (row_ch. coef (i) -
2281 this -> get (row_nr, col_nr));
2282 if (!(e == zero))
2283 this -> add (row_nr, col_nr, e);
2284 }
2285 }
2286
2287 // update the other matrices if necessary
2288 if (!update_linked)
2289 return;
2290 mmatrix<euclidom> *m;
2291 while ((m = img_img. take ()) != NULL)
2292 if ((m -> rows) && (m -> nrows))
2293 m -> mult_left (setRows, setCols, M, invM, false);
2294 while ((m = img_dom. take ()) != NULL)
2295 if ((m -> cols) && (m -> ncols))
2296 m -> mult_right (setCols, setRows, invM, M, false);
2297
2298 return;
2299} /* mmatrix<euclidom>::mult_left */
chomp::homology::mmatrix::getnrows
int_t getnrows() const
Returns the number of rows in the matrix.
Definition: chains.h:1533
chomp::homology::mmatrix::get
euclidom get(int_t row, int_t col) const
Returns the value at the desired location of the matrix.
Definition: chains.h:1495
chomp::homology::mmatrix::mult_right
void mult_right(const int_t setRows[], const int_t setCols[], const mmatrix< euclidom > &M, const mmatrix< euclidom > &invM, bool update_linked)
Multiplies the matrix from the right by an invertible square matrix whose possibly nonzero entries ar...
Definition: chains.h:2303
chomp::homology::mmatrix::getrow
const chain< euclidom > & getrow(int_t n) const
Returns a reference to the entire row stored as a chain.
Definition: chains.h:1517

◆ mult_right()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::mult_right ( const int_t  setRows[],
const int_t  setCols[],
const mmatrix< euclidom > &  M,
const mmatrix< euclidom > &  invM,
bool  update_linked 
)
inlineprivate

Multiplies the matrix from the right by an invertible square matrix whose possibly nonzero entries are only in the given rows and columns.

The matrix provided for multiplication consists only of the selected rows and columns, numbered sequentially from 0. If it is known that the matrix to be multiplied has nonzero entries in the given columns only in the given rows then this information can be provided to speed up the multiplication. If requested, updates the matrices linked to this one.

Definition at line 2302 of file chains.h.

2308{
2309 euclidom zero;
2310 zero = 0;
2311 euclidom one;
2312 one = 1;
2313
2314 // compute the possibly changed columns of the matrix
2315 int_t size = M. getncols ();
2316 auto_array<chain<euclidom> > newCols_p (new chain<euclidom> [size]);
2317 chain<euclidom> *newCols = newCols_p. get ();
2318 for (int_t col = 0; col < size; ++ col)
2319 {
2320 // determine the numbers of rows to process
2321 chain<euclidom> affected;
2322 for (int_t row = 0; row < size; ++ row)
2323 {
2324 const chain<euclidom> &colChain =
2325 this -> getcol (setRows [row]);
2326 int_t colSize = colChain. size ();
2327 for (int cur = 0; cur < colSize; ++ cur)
2328 {
2329 int_t num (colChain. num (cur));
2330 if (affected. findnumber (num) < 0)
2331 affected. add (num, one);
2332 }
2333 }
2334
2335 // multiply these columns by the current row of M
2336 int_t row_count = affected. size ();
2337 for (int_t row = 0; row < row_count; ++ row)
2338 {
2339 int_t row_nr = affected. num (row);
2340 euclidom e;
2341 e = 0;
2342 for (int_t k = 0; k < size; ++ k)
2343 {
2344 int_t col_k = setRows [k]; // sic!
2345 e += this -> get (row_nr, col_k) *
2346 M. get (k, col);
2347 }
2348 if (!(e == 0))
2349 newCols [col]. add (row_nr, e);
2350 }
2351 }
2352
2353 // replace the previous columns in the matrix with the new ones
2354 for (int_t col = 0; col < size; ++ col)
2355 {
2356 int_t col_nr = setCols [col];
2357 const chain<euclidom> &col_ch (newCols [col]);
2358
2359 // eliminate entries that do not appear in the new column
2360 const chain<euclidom> col_prev (this -> getcol (col_nr));
2361 int_t len_prev = col_prev. size ();
2362 for (int_t i = 0; i < len_prev; ++ i)
2363 {
2364 int_t row_nr (col_prev. num (i));
2365 euclidom e (col_ch. getcoefficient (row_nr));
2366 if (e == zero)
2367 {
2368 euclidom coef (this -> get (row_nr, col_nr));
2369 this -> add (row_nr, col_nr, -coef);
2370 }
2371 }
2372
2373 // set the other entries to the ones in the new column
2374 int_t len = col_ch. size ();
2375 for (int_t i = 0; i < len; ++ i)
2376 {
2377 int_t row_nr (col_ch. num (i));
2378 euclidom e (col_ch. coef (i) -
2379 this -> get (row_nr, col_nr));
2380 if (!(e == zero))
2381 this -> add (row_nr, col_nr, e);
2382 }
2383 }
2384
2385 // update the other matrices if necessary
2386 if (!update_linked)
2387 return;
2388 mmatrix<euclidom> *m;
2389 while ((m = dom_dom. take ()) != NULL)
2390 if ((m -> cols) && (m -> ncols))
2391 m -> mult_left (setRows, setCols, M, invM, false);
2392 while ((m = dom_img. take ()) != NULL)
2393 if ((m -> rows) && (m -> nrows))
2394 m -> mult_right (setCols, setRows, invM, M, false);
2395
2396 return;
2397} /* mmatrix<euclidom>::mult_right */
chomp::homology::mmatrix::getcol
const chain< euclidom > & getcol(int_t n) const
Returns a reference to the entire column stored as a chain.
Definition: chains.h:1525
chomp::homology::mmatrix::getncols
int_t getncols() const
Returns the number of columns in the matrix.
Definition: chains.h:1539

◆ multiply()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::multiply ( const mmatrix< euclidom > &  m1,
const mmatrix< euclidom > &  m2 
)
inline

Computes the product of the two given matrices.

The matrix is replaced with the product.

Definition at line 2502 of file chains.h.

2504{
2505 if (m1. ncols != m2. nrows)
2506 throw "Trying to multiply matrices of wrong sizes.";
2507 int_t K = m1. ncols;
2508 define (m1. nrows, m2. ncols);
2509 for (int_t i = 0; i < nrows; ++ i)
2510 {
2511 for (int_t j = 0; j < ncols; ++ j)
2512 {
2513 euclidom e;
2514 e = 0;
2515 for (int_t k = 0; k < K; ++ k)
2516 e += m1. get (i, k) * m2. get (k, j);
2517 add (i, j, e);
2518 }
2519 }
2520 return;
2521} /* mmatrix<euclidom>::multiply */

◆ multiplycol()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::multiplycol ( int_t  n,
const euclidom &  e 
)
inline

Multiplies the column by the given coefficient and updates rows.

Definition at line 1669 of file chains.h.

1670{
1671 // retrieve the row
1672 chain<euclidom> &thecol = cols [n];
1673
1674 // multiply the row
1675 thecol. multiply (e);
1676
1677 // multiply the corresponding entries in all the rows
1678 for (int_t i = 0; i < thecol. size (); ++ i)
1679 rows [thecol. num (i)]. multiply (e, n);
1680
1681 return;
1682} /* mmatrix<euclidom>::multiplycol */
chomp::homology::mmatrix::multiply
void multiply(const mmatrix< euclidom > &m1, const mmatrix< euclidom > &m2)
Computes the product of the two given matrices.
Definition: chains.h:2502

◆ multiplyrow()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::multiplyrow ( int_t  n,
const euclidom &  e 
)
inline

Multiplies the row by the given coefficient and updates columns.

Definition at line 1653 of file chains.h.

1654{
1655 // retrieve the row
1656 chain<euclidom> &therow = rows [n];
1657
1658 // multiply the row
1659 therow. multiply (e);
1660
1661 // multiply the corresponding entries in all the columns
1662 for (int_t i = 0; i < therow. size (); ++ i)
1663 cols [therow. num (i)]. multiply (e, n);
1664
1665 return;
1666} /* mmatrix<euclidom>::multiplyrow */

◆ operator=()

template<class euclidom >
mmatrix< euclidom > & chomp::homology::mmatrix< euclidom >::operator= ( const mmatrix< euclidom > &  s)
inline

The assignment operator.

Added by Marcin Zelawski and fixed by Pawel Pilarczyk.

Definition at line 1412 of file chains.h.

1414{
1415 // first release allocated tables if any
1416 if (rows)
1417 delete [] rows;
1418 if (cols)
1419 delete [] cols;
1420
1421 nrows = m. nrows;
1422 ncols = m. ncols;
1423 allrows = m. allrows;
1424 allcols = m. allcols;
1425
1426 rows = NULL;
1427 cols = NULL;
1428 if (m. allrows > 0)
1429 {
1430 chain<euclidom> *newrows = new chain<euclidom> [m. allrows];
1431 if (!newrows)
1432 throw "Not enough memory for matrix rows.";
1433 for (int_t i = 0; i < m. allrows; ++ i)
1434 newrows [i] = m. rows [i];
1435 rows = newrows;
1436 }
1437
1438 if (m. allcols > 0)
1439 {
1440 chain<euclidom> *newcols = new chain<euclidom> [m. allcols];
1441 if (!newcols)
1442 throw "Not enough memory for matrix columns.";
1443 for (int_t i = 0; i < m.allcols; ++ i)
1444 newcols [i] = m. cols [i];
1445 cols = newcols;
1446 }
1447
1448 return *this;
1449} /* mmatrix<euclidom>::operator = */

◆ reducecol()

template<class euclidom >
int_t chomp::homology::mmatrix< euclidom >::reducecol ( int_t  n,
int_t  preferred 
)
inline

Reduces the given column of the matrix and updates its rows.

A preferred number of a row to leave is given. Updates all the matrices which are linked to this one. Returns the number of the row to be reduced next, or -1 if done.

Definition at line 1817 of file chains.h.

1818{
1819 if (n >= ncols)
1820 throw "Trying to reduce a column out of range.";
1821
1822 int_t the_other = -1;
1823
1824 // repeat until the column contains at most one nonzero entry
1825 int_t len;
1826 while ((len = cols [n]. size ()) > 1)
1827 {
1828 // copy the column to a local structure
1829 chain<euclidom> local (cols [n]);
1830
1831 // find the best element in this column
1832 int_t best_i = local. findbest (rows);
1833
1834 // find the number of the preferred element in the row
1835 int_t preferred_i = (preferred < 0) ? -1 :
1836 local. findnumber (preferred);
1837
1838 // check if the element in the preferred column
1839 // is equally good as the one already chosen
1840 if ((preferred_i >= 0) &&
1841 (local. coef (preferred_i). delta () ==
1842 local. coef (best_i). delta ()))
1843 best_i = preferred_i;
1844
1845 // remember the row number containing this element
1846 the_other = local. num (best_i);
1847
1848 // for each row
1849 for (int_t i = 0; i < len; ++ i)
1850 {
1851 // if this row is the chosen one, do nothing
1852 if (i == best_i)
1853 continue;
1854
1855 // compute the quotient of two elements
1856 euclidom quotient = local. coef (i) /
1857 local. coef (best_i);
1858
1859 // subtract the chosen row from the other one
1860 addrow (local. num (i), local. num (best_i),
1861 -quotient);
1862 }
1863 }
1864
1865 return the_other;
1866} /* mmatrix<euclidom>::reducecol */

◆ reducerow()

template<class euclidom >
int_t chomp::homology::mmatrix< euclidom >::reducerow ( int_t  n,
int_t  preferred 
)
inline

Reduces the given row of the matrix and updates its columns.

A preferred number of a column to leave is given. Updates all the matrices which are linked to this one. Returns the number of the column to be reduced next, or -1 if done.

Definition at line 1765 of file chains.h.

1766{
1767 if (n >= nrows)
1768 throw "Trying to reduce a row out of range.";
1769
1770 int_t the_other = -1;
1771
1772 // repeat until the row contains at most one nonzero entry
1773 int_t len;
1774 while ((len = rows [n]. size ()) > 1)
1775 {
1776 // copy the row to a local structure
1777 chain<euclidom> local (rows [n]);
1778
1779 // find the best element in this row
1780 int_t best_i = local. findbest (cols);
1781
1782 // find the number of the preferred element in the row
1783 int_t preferred_i = (preferred < 0) ? -1 :
1784 local. findnumber (preferred);
1785
1786 // check if the element in the preferred column
1787 // is equally good as the one already chosen
1788 if ((preferred_i >= 0) &&
1789 (local. coef (preferred_i). delta () ==
1790 local. coef (best_i). delta ()))
1791 best_i = preferred_i;
1792
1793 // remember the column number containing this element
1794 the_other = local. num (best_i);
1795
1796 // for each column
1797 for (int_t i = 0; i < len; ++ i)
1798 {
1799 // if this column is the chosen one, do nothing
1800 if (i == best_i)
1801 continue;
1802
1803 // compute the quotient of two elements
1804 euclidom quotient = local. coef (i) /
1805 local. coef (best_i);
1806
1807 // subtract the chosen column from the other one
1808 addcol (local. num (i), local. num (best_i),
1809 -quotient);
1810 }
1811 }
1812
1813 return the_other;
1814} /* mmatrix<euclidom>::reducerow */

◆ show_hom_col() [1/2]

template<class euclidom >
outputstream & chomp::homology::mmatrix< euclidom >::show_hom_col ( outputstream &  out,
int_t  col,
const chain< euclidom > &  range,
const char *  txt = NULL 
) const
inline

Writes a column with only these coefficients which exist in 'range', and shows their positions in that chain.

Definition at line 2542 of file chains.h.

2544{
2545 // keep current position in 'range'
2546 int_t j = 0;
2547
2548 // remember if this is the first displayed element
2549 int_t first = 1;
2550
2551 // go through the column of the matrix
2552 for (int_t i = 0; i < cols [col]. size (); ++ i)
2553 {
2554 // find the current element in the range
2555 while ((j < range. size ()) &&
2556 (range. num (j) < cols [col]. num (i)))
2557 {
2558 ++ j;
2559 }
2560
2561 // if this element was found in the range, display it
2562 if ((j < range. size ()) &&
2563 (range. num (j) == cols [col]. num (i)))
2564 {
2565 if (first)
2566 first = 0;
2567 else
2568 out << " + ";
2569 if (-cols [col]. coef (i) == 1)
2570 out << "-";
2571 else if (cols [col]. coef (i) != 1)
2572 out << cols [col]. coef (i) << " * ";
2573 if (txt)
2574 out << txt;
2575 out << (j + 1);
2576 }
2577 }
2578
2579 // if nothing was shown, display 0
2580 if (first)
2581 out << 0;
2582
2583 return out;
2584} /* mmatrix<euclidom>::show_hom_col */

◆ show_hom_col() [2/2]

template<class euclidom >
std::ostream & chomp::homology::mmatrix< euclidom >::show_hom_col ( std::ostream &  out,
int_t  col,
const chain< euclidom > &  range,
const char *  txt = NULL 
) const
inline

Writes a column with only these coefficients which exist in 'range', and shows their positions in that chain.

Definition at line 2587 of file chains.h.

2589{
2590 outputstream tout (out);
2591 show_hom_col (tout, col, range, txt);
2592 return out;
2593} /* mmatrix<euclidom>::show_hom_col */
chomp::homology::mmatrix::show_hom_col
outputstream & show_hom_col(outputstream &out, int_t col, const chain< euclidom > &range, const char *txt=NULL) const
Writes a column with only these coefficients which exist in 'range', and shows their positions in tha...
Definition: chains.h:2542

◆ showcols() [1/2]

template<class euclidom >
outputstream & chomp::homology::mmatrix< euclidom >::showcols ( outputstream &  out,
int_t  first = 0,
int_t  howmany = 0,
const char *  label = "Col " 
) const
inline

Writes the matrix to an output stream by its rows.

Definition at line 1901 of file chains.h.

1903{
1904 return showrowscols (out, cols, ncols, first, howmany, label);
1905} /* mmatrix<euclidom>::showcols */
chomp::homology::mmatrix::showrowscols
outputstream & showrowscols(outputstream &out, chain< euclidom > *table, int_t tablen, int_t first=0, int_t howmany=0, const char *label=NULL) const
Writes the matrix to an output stream by its rows or columns.
Definition: chains.h:1869

◆ showcols() [2/2]

template<class euclidom >
std::ostream & chomp::homology::mmatrix< euclidom >::showcols ( std::ostream &  out,
int_t  first = 0,
int_t  howmany = 0,
const char *  label = "Col " 
) const
inline

Writes the matrix to an output stream by its rows.

Definition at line 1908 of file chains.h.

1910{
1911 outputstream tout (out);
1912 showcols (tout, first, howmany, label);
1913 return out;
1914} /* mmatrix<euclidom>::showcols */
chomp::homology::mmatrix::showcols
outputstream & showcols(outputstream &out, int_t first=0, int_t howmany=0, const char *label="Col ") const
Writes the matrix to an output stream by its rows.
Definition: chains.h:1901

◆ showmap() [1/2]

template<class euclidom >
outputstream & chomp::homology::mmatrix< euclidom >::showmap ( outputstream &  out,
const char *  maplabel = NULL,
const char *  xlabel = NULL,
const char *  ylabel = NULL 
) const
inline

Writes the matrix as a linear map on generators.

Definition at line 1917 of file chains.h.

1919{
1920 if (ncols <= 0)
1921 {
1922 if (maplabel && (maplabel [0] == '\t'))
1923 out << "\t0\n";
1924 else
1925 out << "0\n";
1926 }
1927 for (int_t i = 0; i < ncols; ++ i)
1928 {
1929 out << (maplabel ? maplabel : "f") << " (" <<
1930 (xlabel ? xlabel : "") << (i + 1) << ") = ";
1931 cols [i]. show (out, ylabel) << '\n';
1932 }
1933 return out;
1934} /* mmatrix<euclidom>::showmap */

◆ showmap() [2/2]

template<class euclidom >
std::ostream & chomp::homology::mmatrix< euclidom >::showmap ( std::ostream &  out,
const char *  maplabel = NULL,
const char *  xlabel = NULL,
const char *  ylabel = NULL 
) const
inline

Writes the matrix as a linear map on generators.

Definition at line 1937 of file chains.h.

1939{
1940 outputstream tout (out);
1941 showmap (tout, maplabel, xlabel, ylabel);
1942 return out;
1943} /* mmatrix<euclidom>::showmap */
chomp::homology::mmatrix::showmap
outputstream & showmap(outputstream &out, const char *maplabel=NULL, const char *xlabel=NULL, const char *ylabel=NULL) const
Writes the matrix as a linear map on generators.
Definition: chains.h:1917

◆ showrows() [1/2]

template<class euclidom >
outputstream & chomp::homology::mmatrix< euclidom >::showrows ( outputstream &  out,
int_t  first = 0,
int_t  howmany = 0,
const char *  label = "Row " 
) const
inline

Writes the matrix to an output stream by its rows.

Definition at line 1885 of file chains.h.

1887{
1888 return showrowscols (out, rows, nrows, first, howmany, label);
1889} /* mmatrix<euclidom>::showrows */

◆ showrows() [2/2]

template<class euclidom >
std::ostream & chomp::homology::mmatrix< euclidom >::showrows ( std::ostream &  out,
int_t  first = 0,
int_t  howmany = 0,
const char *  label = "Row " 
) const
inline

Writes the matrix to an output stream by its rows.

Definition at line 1892 of file chains.h.

1894{
1895 outputstream tout (out);
1896 showrows (tout, first, howmany, label);
1897 return out;
1898} /* mmatrix<euclidom>::showrows */
chomp::homology::mmatrix::showrows
outputstream & showrows(outputstream &out, int_t first=0, int_t howmany=0, const char *label="Row ") const
Writes the matrix to an output stream by its rows.
Definition: chains.h:1885

◆ showrowscols()

template<class euclidom >
outputstream & chomp::homology::mmatrix< euclidom >::showrowscols ( outputstream &  out,
chain< euclidom > *  table,
int_t  tablen,
int_t  first = 0,
int_t  howmany = 0,
const char *  label = NULL 
) const
inline

Writes the matrix to an output stream by its rows or columns.

Definition at line 1869 of file chains.h.

1872{
1873 if ((first < 0) || (first >= tablen))
1874 first = 0;
1875 if ((howmany <= 0) || (first + howmany > tablen))
1876 howmany = tablen - first;
1877 for (int_t i = 0; i < howmany; ++ i)
1878 out << (label ? label : "") << (first + i + 1) << ": " <<
1879 table [first + i] << '\n';
1880 out << '\n';
1881 return out;
1882} /* matrix<euclidom>::showrowscols */

◆ simple_form()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::simple_form ( bool  quiet = false)
inline

Transforms the matrix to a simple form (nearly SNF).

Updates all the matrices which are linked to this one.

Definition at line 2003 of file chains.h.

2004{
2005 // if the matrix has no rows or columns, it is already in simple form
2006 if (!nrows || !ncols)
2007 return;
2008
2009 // make some random simple reductions before proceeding
2010 simple_reductions (quiet);
2011
2012 // prepare a counter
2013 long count = 0;
2014
2015 // prepare variables for chosen row and column numbers
2016 int_t row, col, prev_row, prev_col;
2017
2018 // find a row or a column with at least two nonzero entries
2019 row = -1;
2020 col = findcol (2);
2021 prev_row = -1, prev_col = -1;
2022 if (col < 0)
2023 row = findrow (2);
2024
2025 // repeat while such a row or a column can be found
2026 while ((row >= 0) || (col >= 0))
2027 {
2028 // reduce rows and columns until a single entry remains
2029 while ((row >= 0) || (col >= 0))
2030 if (row >= 0)
2031 {
2032 col = reducerow (row, prev_col);
2033 prev_row = row;
2034 row = -1;
2035 }
2036 else if (col >= 0)
2037 {
2038 row = reducecol (col, prev_row);
2039 prev_col = col;
2040 col = -1;
2041 }
2042
2043 // update the counter and display it if requested to
2044 ++ count;
2045 if (!quiet && !(count % 373))
2046 scon << std::setw (12) << count <<
2047 "\b\b\b\b\b\b\b\b\b\b\b\b";
2048
2049 // find another row or column with at least 2 nonzero entries
2050 col = findcol (2);
2051 if (col < 0)
2052 row = findrow (2);
2053 }
2054
2055 if (!quiet)
2056 sout << " " << count << " reductions made. ";
2057
2058 return;
2059} /* mmatrix<euclidom>::simple_form */
chomp::homology::mmatrix::reducerow
int_t reducerow(int_t n, int_t preferred)
Reduces the given row of the matrix and updates its columns.
Definition: chains.h:1765
chomp::homology::mmatrix::reducecol
int_t reducecol(int_t n, int_t preferred)
Reduces the given column of the matrix and updates its rows.
Definition: chains.h:1817
chomp::homology::mmatrix::simple_reductions
void simple_reductions(bool quiet=false)
Runs some random simple reductions.
Definition: chains.h:1946
chomp::homology::mmatrix::findrow
int_t findrow(int_t req_elements=1, int_t start=-1) const
Finds a row containing at least the required number of nonzero elements, starting at the given row.
Definition: chains.h:1753
chomp::homology::mmatrix::findcol
int_t findcol(int_t req_elements=1, int_t start=-1) const
Finds a column containing at least the required number of nonzero elements, starting at the given col...
Definition: chains.h:1759
chomp::homology::sout
outputstream sout
A replacement for standard output stream, with optional logging and other features provided by the cl...
chomp::homology::scon
outputstream scon
The console output stream to which one should put all the junk that spoils the log file,...

References chomp::homology::scon, and chomp::homology::sout.

◆ simple_form_to_SNF()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::simple_form_to_SNF ( bool  quiet = false)
inline

Transforms the matrix from the simple form to actual SNF.

Calls "arrange_towards_SNF" first, and then makes appropriate corrections of the coefficients at the "diagonal" so that each nonzero coefficient divides its successor. Assumes that the matrix is already in the simple form. Updates all the matrices which are linked to this one. WARNING: SEEMS NOT TO WORK CORRECTLY AT THE MOMENT.

Definition at line 2103 of file chains.h.

2104{
2105 // arrange towards SNF
2106 if (!quiet)
2107 sout << "Determining the 'diagonal'... ";
2108 int_t indexBegin = 0;
2109 int_t indexEnd = arrange_towards_SNF (&indexBegin);
2110 if (!quiet)
2111 {
2112 sout << indexBegin << " invertible + " <<
2113 (indexEnd - indexBegin) << " noninvertible coefs.\n";
2114 }
2115
2116 // check the division condition and make corrections where necessary
2117 if (!quiet)
2118 sout << "Correcting the division condition... ";
2119 int_t countCorrections = 0;
2120 bool divisionOK = false;
2121 euclidom zero;
2122 zero = 0;
2123 while (!divisionOK)
2124 {
2125 divisionOK = true;
2126 for (int_t index = indexBegin + 1; index < indexEnd; ++ index)
2127 {
2128 euclidom e1 (this -> get (index - 1, index - 1));
2129 euclidom e2 (this -> get (index, index));
2130 if (e2 % e1 == zero)
2131 continue;
2132 divisionOK = false;
2133 // sout << "\nDEBUG: " << e1 << " does not divide " <<
2134 // e2 << " at position " << (index - 1) << ".\n";
2135 division_SNF_correction (e1, index - 1, e2, index);
2136 ++ countCorrections;
2137 }
2138 }
2139 sout << countCorrections << " corrections.\n";
2140 return;
2141} /* mmatrix<euclidom>::simple_form_to_SNF */
chomp::homology::mmatrix::arrange_towards_SNF
int_t arrange_towards_SNF(int_t *invertible_count=0)
Swaps rows and columns to make the simple form closer to SNF.
Definition: chains.h:2062
chomp::homology::mmatrix::division_SNF_correction
void division_SNF_correction(const euclidom &a, int_t pos1, const euclidom &b, int_t pos2)
Makes a correction of division in the "diagonal" at the given two positions, so that the entry at pos...
Definition: chains.h:2145

References chomp::homology::sout.

◆ simple_reductions()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::simple_reductions ( bool  quiet = false)
inline

Runs some random simple reductions.

Updates all the matrices which are linked to this one. This function is launched at the beginning of the 'simple_form' procedure.

Definition at line 1946 of file chains.h.

1947{
1948 // if the matrix has no rows or no columns,
1949 // simple reductions make no sense
1950 if (!nrows || !ncols)
1951 return;
1952
1953 // prepare counters
1954 long countreduced = 0;
1955 long count = 4 * ((nrows > ncols) ? ncols : nrows);
1956
1957 // prepare quazi-random numbers
1958 int_t nr = static_cast<int_t> (std::rand () % nrows);
1959 if (nr < 0)
1960 nr = 1 - nr;
1961 int_t nr_count = 0;
1962 int_t nr_add = 0;
1963
1964 // try quazi-random reductions
1965 while (count --)
1966 {
1967 // try a simple reduction
1968 if ((rows [nr]. size () == 1) &&
1969 (rows [nr]. coef (0). delta () == 1) &&
1970 (cols [rows [nr]. num (0)]. size () > 1))
1971 {
1972 ++ countreduced;
1973 reducecol (rows [nr]. num (0), -1);
1974 }
1975
1976 // try a new semi-random position
1977 if (nr_count)
1978 -- nr_count;
1979 else
1980 {
1981 nr_add = ((std::rand () >> 2) + 171) % nrows;
1982 if (nr_add < 1)
1983 nr_add = 1;
1984 nr_count = 100;
1985 }
1986 nr += nr_add;
1987 if (nr >= nrows)
1988 nr -= nrows;
1989
1990 // display a counter
1991 if (!quiet && !(count % 373))
1992 scon << std::setw (12) << count <<
1993 "\b\b\b\b\b\b\b\b\b\b\b\b";
1994 }
1995
1996 if (!quiet)
1997 sout << countreduced << " +";
1998
1999 return;
2000} /* mmatrix<euclidom>::simple_reductions */

References chomp::homology::scon, and chomp::homology::sout.

◆ submatrix()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::submatrix ( const mmatrix< euclidom > &  matr,
const chain< euclidom > &  domain,
const chain< euclidom > &  range 
)
inline

Extracts a submatrix from the given matrix.

Uses the positions in the 'domain' and 'range' chains as the column and row numbers for the coefficients in the new matrix.

Definition at line 2524 of file chains.h.

2526{
2527 for (int_t i = 0; i < domain. size (); ++ i)
2528 {
2529 for (int_t j = 0; j < range. size (); ++ j)
2530 {
2531 euclidom e = matr. get (domain. num (i),
2532 range. num (j));
2533 if (!(e == 0))
2534 add (i, j, e);
2535 }
2536 }
2537
2538 return;
2539} /* mmatrix<euclidom>::submatrix */

◆ swapcols()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::swapcols ( int_t  i,
int_t  j 
)
inline

Swaps two columns of the matrix.

Updates all the matrices which are linked to this one.

Definition at line 1626 of file chains.h.

1627{
1628 // in the trivial case nothing needs to be done
1629 if (i == j)
1630 return;
1631
1632 // check if the parameters are not out of range
1633 if ((i < 0) || (i >= ncols) || (j < 0) || (j >= ncols))
1634 throw "Trying to swap cols out of range.";
1635
1636 // swap the columns
1637 cols [i]. swap (cols [j], i, j, rows);
1638
1639 // update the other matrices
1640 mmatrix<euclidom> *m;
1641 while ((m = dom_dom. take ()) != NULL)
1642 if ((m -> cols) && (m -> ncols))
1643 m -> cols [i]. swap (m -> cols [j], i, j, m -> rows);
1644
1645 while ((m = dom_img. take ()) != NULL)
1646 if ((m -> rows) && (m -> nrows))
1647 m -> rows [i]. swap (m -> rows [j], i, j, m -> cols);
1648
1649 return;
1650} /* mmatrix<euclidom>::swapcols */
chomp::multiwork::swap
void swap(mwWorkerData &data1, mwWorkerData &data2)
Definition: mwcoord.h:108

References chomp::multiwork::swap().

◆ swaprows()

template<class euclidom >
void chomp::homology::mmatrix< euclidom >::swaprows ( int_t  i,
int_t  j 
)
inline

Swaps two rows of the matrix.

Updates all the matrices which are linked to this one.

Definition at line 1599 of file chains.h.

1600{
1601 // in the trivial case nothing needs to be done
1602 if (i == j)
1603 return;
1604
1605 // check if the parameters are not out of range
1606 if ((i < 0) || (i >= nrows) || (j < 0) || (j >= nrows))
1607 throw "Trying to swap rows out of range.";
1608
1609 // swap the rows
1610 rows [i]. swap (rows [j], i, j, cols);
1611
1612 // update the other matrices
1613 mmatrix<euclidom> *m;
1614 while ((m = img_img. take ()) != NULL)
1615 if ((m -> rows) && (m -> nrows))
1616 m -> rows [i]. swap (m -> rows [j], i, j, m -> cols);
1617
1618 while ((m = img_dom. take ()) != NULL)
1619 if ((m -> cols) && (m -> ncols))
1620 m -> cols [i]. swap (m -> cols [j], i, j, m -> rows);
1621
1622 return;
1623} /* mmatrix<euclidom>::swaprows */

References chomp::multiwork::swap().

Member Data Documentation

◆ allcols

template<class euclidom >
int_t chomp::homology::mmatrix< euclidom >::allcols
private

The number of allocated columns.

Definition at line 1271 of file chains.h.

Referenced by chomp::homology::mmatrix< euclidom >::mmatrix().

◆ allrows

template<class euclidom >
int_t chomp::homology::mmatrix< euclidom >::allrows
private

The number of allocated rows.

Definition at line 1268 of file chains.h.

Referenced by chomp::homology::mmatrix< euclidom >::mmatrix().

◆ cols

template<class euclidom >
chain<euclidom>* chomp::homology::mmatrix< euclidom >::cols
private

The columns of the matrix.

Definition at line 1277 of file chains.h.

◆ dom_dom

template<class euclidom >
simplelist<mmatrix<euclidom> > chomp::homology::mmatrix< euclidom >::dom_dom

This is a list of matrices to be updated together with the changes to the columns or rows of the current matrix.

These matrices may have these spaces as their domains or ranges (codomains, images). For instance, "dom_img" is a list of matrices such that the domain of the current matrix is the image of each of them.

Definition at line 1205 of file chains.h.

◆ dom_img

template<class euclidom >
simplelist<mmatrix<euclidom> > chomp::homology::mmatrix< euclidom >::dom_img

Definition at line 1205 of file chains.h.

◆ img_dom

template<class euclidom >
simplelist<mmatrix<euclidom> > chomp::homology::mmatrix< euclidom >::img_dom

Definition at line 1205 of file chains.h.

◆ img_img

template<class euclidom >
simplelist<mmatrix<euclidom> > chomp::homology::mmatrix< euclidom >::img_img

Definition at line 1206 of file chains.h.

◆ ncols

template<class euclidom >
int_t chomp::homology::mmatrix< euclidom >::ncols
private

The number of columns in the matrix.

Definition at line 1265 of file chains.h.

Referenced by chomp::homology::mmatrix< euclidom >::mmatrix().

◆ nrows

template<class euclidom >
int_t chomp::homology::mmatrix< euclidom >::nrows
private

The number of rows in the matrix.

Definition at line 1262 of file chains.h.

Referenced by chomp::homology::mmatrix< euclidom >::mmatrix().

◆ rows

template<class euclidom >
chain<euclidom>* chomp::homology::mmatrix< euclidom >::rows
private

The rows of the matrix.

Definition at line 1274 of file chains.h.

The documentation for this class was generated from the following file:
Generated by doxygen 1.9.4