chaincon/homgvf3.h

Go to the documentation of this file.

/////////////////////////////////////////////////////////////////////////////
///
/// \file
///
/// Homology gradient vector field computation: Algorithm 3, using the SNF.
///
/////////////////////////////////////////////////////////////////////////////

// Copyright (C) 2009-2011 by Pawel Pilarczyk.
//
// This file is part of my research software package. This is free software:
// you can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation,
// either version 3 of the License, or (at your option) any later version.
//
// This software is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this software; see the file "license.txt". If not,
// please, see <http://www.gnu.org/licenses/>.

// Started on March 24, 2009. Last revision: March 24, 2011.


#ifndef _CHAINCON_HOMGVF3_H_
#define _CHAINCON_HOMGVF3_H_


// include some standard C++ header files
#include <istream>
#include <ostream>

// include selected header files from the CHomP library
#include "chomp/system/config.h"
#include "chomp/system/timeused.h"
#include "chomp/system/textfile.h"
#include "chomp/struct/hashsets.h"
#include "chomp/struct/multitab.h"
#include "chomp/struct/integer.h"
#include "chomp/homology/chains.h"

// include relevant local header files
#include "chaincon/combchain.h"
#include "chaincon/comblinmap.h"


// --------------------------------------------------
// ------------------ Homology GVF ------------------
// --------------------------------------------------

/// Verifies if the given mmatrix is an identity
inline bool is_identity (const chomp::homology::mmatrix
        <chomp::homology::integer> &M)
{
        int nCols = M. getncols ();
        for (int col = 0; col < nCols; ++ col)
        {
                const chomp::homology::chain<chomp::homology::integer>
                        &column = M. getcol (col);
                if (column. size () != 1)
                        return false;
                if (column. num (0) != col)
                        return false;
        }
        return true;
} /* is_identity */

/// Computes the homology gradient vector field for the given
/// filtered finite cell complex "K".
/// Cells that represent homology generators are appended to the vector "H".
/// The projection map "pi", the inclusion from "H" to the complex "K",
/// and the homology gradient vector field "phi"
/// are assumed to be initially zero and are constructed.
template <class CellT, class CellArray1, class CellArray2>
void homologyGVF3 (const CellArray1 &K, CellArray2 &H,
        tCombLinMap<CellT,CellT> &pi,
        tCombLinMap<CellT,CellT> &incl,
        tCombLinMap<CellT,CellT> &phi)
{
        using chomp::homology::chaincomplex;
        using chomp::homology::chain;
        using chomp::homology::mmatrix;
        using chomp::homology::timeused;
        using chomp::homology::sout;
//      using chomp::homology::scon;
        using chomp::homology::integer;
        using chomp::homology::hashedset;
        using chomp::homology::multitable;

        // don't do anything for an empty complex
        if (K. empty ())
                return;

        // start measuring total computation time of this routine
        timeused compTime;
        compTime = 0;

        // construct a chain complex
        sout << "Constructing the chain complex of K...\n";
        timeused constrTime;
        constrTime = 0;

        // set up the ring of coefficients Z_2
        integer::initialize (2);
        integer zero;
        zero = 0;
        integer one;
        one = 1;

        // create the chain complex
        int_t KSize = K. size ();
        int dim = K [KSize - 1]. dim ();
        chaincomplex<integer> cx (dim, 1, 1);

        // go through all the cells in the filter and compute boundaries
        multitable<hashedset<CellT> > cells;
        for (int_t i = 0; i < KSize; ++ i)
        {
                // retrieve the i-th cell in the filter
                const CellT &c = K [i];

                // determine the dimension of this cell
                int d = c. dim ();

                // add the cell to the right array of cells
                int_t cNum = cells [d]. size ();
                cells [d]. add (c);

                // compute the boundary of this cell
                int_t bLen = c. boundaryLength ();
                for (int_t j = 0; j < bLen; ++ j)
                {
                        // create the j-th boundary cell
                        CellT bCell (c, j);

                        // ignore the coefficient (temporarily)
                        // int bCoef = c. boundaryCoef (j);

                        // determine the number of the boundary cell
                        int_t bNum = cells [d - 1]. getnumber (bCell);

                        // add the boundary relation to the chain complex
                        cx. add (d, bNum, cNum, one);
                }
        }

        // make sure that the size of the chain complex is enough
        for (int d = 0; d <= dim; ++ d)
        {
                cx. def_gen (d, cells [d]. size ());
        }

        // show timing information
        sout << "The chain complex created in " << constrTime << ".\n";

        // compute the SNF
        sout << "Computing the SNF of the boundary operator...\n";
        timeused snfTime;
        snfTime = 0;

        int *level = 0;
        bool quiet = false;
        cx. simple_form (level, quiet);

        // DEBUG: Check if the change of basis matrices are correct.
        if (false)
        {
                sout << "DEBUG CHECK: change of basis (this will take "
                        "a while)...\n";
                for (int q = 0; q <= dim; ++ q)
                {
                        mmatrix<integer> M, N;
                        M. multiply (cx. gethomgen (q),
                                cx. getchgbasis (q));
                        N. multiply (cx. getchgbasis (q),
                                cx. gethomgen (q));
                        if (!is_identity (M) || !is_identity (N))
                        {
                                sout << "\nDEBUG ERROR: Wrong change of basis "
                                        "detected at level " << q << ".\n";
                        }
                }
                sout << "Note: The change of basis matrices were verified "
                        "successfully.\n";
        }

        // show timing information
        sout << "The SNF computed in " << snfTime << ".\n";

        // compute the g.v.f. together with the projection and the inclusion
        sout << "Composing a homology gradient vector field "
                "from the SNF...\n";
        timeused gvfTime;
        gvfTime = 0;

        // prepare the lists of chain complex generators
        // which are also homology generators
//      multitable <hashedset<int_t> > homGener;

        // prepare the matrices for psi
        multitable <mmatrix<integer> > psi;

        // scan through the entire chain complex in the SNF
        const mmatrix<integer> zeroMatrix;
        for (int q = 0; q <= dim; ++ q)
        {
                // get the matrices computed for the Smith Normal Form:
                // the boundary at level q
                const mmatrix<integer> &Dq = cx. getboundary (q);
                // the boundary at level q + 1
                const mmatrix<integer> &Dq1 = (q < dim) ?
                        cx. getboundary (q + 1) : zeroMatrix;
                // the change of basis from the new one to the original one
                const mmatrix<integer> &Gq = cx. gethomgen (q);
                // the change of basis from the original one to the new one
                const mmatrix<integer> &Aq = cx. getchgbasis (q);

                // set the size of the matrix psi in dimension q - 1
                if (q)
                {
                        psi [q - 1]. define (cells [q]. size (),
                                cells [q - 1]. size ());
                }

                // process the bases of the chain complex in the SNF
                int ncells = cells [q]. size ();
                for (int i = 0; i < ncells; ++ i)
                {
                        // get the column of the matrix Dq
                        const chain<integer> &column = Dq. getcol (i);

                        // if the column in the SNF is nonzero (coef in Z_2!)
                        if (!column. empty ())
                        {
                                int b = column. num (0);
                                if (!q)
                                        throw "Negative psi index.";
                                psi [q - 1]. add (i, b, one);
                        }
                        
                        // if the column in the SNF is zero
                        else if ((q == dim) || (Dq1. getrow (i). empty ()))
                        {
                                // add the number of this cell
                                // to the list of homology generators
                        //      homGener [q]. add (i);

                                // determine the real homology generator
                                const chain<integer> &genChain =
                                        Gq. getcol (i);

                                // take the first entry as a representant
                                const CellT &repr =
                                        cells [q] [genChain. num (0)];
                                H. push_back (repr);

                                // compute the inclusion map on it
                                int_t genSize = genChain. size ();
                                for (int_t j = 0; j < genSize; ++ j)
                                {
                                        int_t n = genChain. num (j);
                                        const CellT &genCell = cells [q] [n];
                                        incl. add (repr, genCell);
                                }

                                // add this term to the projection
                                const chain<integer> &piRow =
                                        Aq. getrow (i);
                                int_t piRowSize = piRow. size ();
                                for (int_t j = 0; j < piRowSize; ++ j)
                                {
                                        int_t num = piRow. num (j);
                                        const CellT &cell = cells [q] [num];
                                        pi. add (cell, repr);
                                }
                        }
                }
        }

        // compute the matrices for phi_q and compose them into one map:
        // \phi_{q - 1} := A^{-1}_q \circ \psi_{q - 1} \circ A_{q - 1}
        sout << "Transferring the computed gvf to the original basis...\n";
        for (int q = 1; q <= dim; ++ q)
        {
                // consider the three matrices to be multiplied
                const mmatrix<integer> &M_A = cx. getchgbasis (q - 1);
                const mmatrix<integer> &M_psi = psi [q - 1];
                const mmatrix<integer> &M_A1 = cx. gethomgen (q);

                // determine the numbers of columns in the matrices
                int_t sizeA = M_A. getncols ();
                int_t sizePsi = M_psi. getncols ();
                int_t sizeA1 = M_A1. getncols ();

                // for all the columns in the first matrix on the right...
                for (int_t i = 0; i < sizeA; ++ i)
                {
                        // take the column
                        const chain<integer> &column = M_A. getcol (i);

                        // compute its image by psi
                        chain<integer> psiC;
                        int_t sizeC = column. size ();
                        for (int_t j = 0; j < sizeC; ++ j)
                        {
                                int_t n = column. num (j);
                                if (n >= sizePsi)
                                        continue;
                                psiC. add (M_psi. getcol (n), one);
                        }

                        // compute the image of this image by A1
                        chain<integer> phiColumn;
                        int_t sizePsiC = psiC. size ();
                        for (int j = 0; j < sizePsiC; ++ j)
                        {
                                int_t n = psiC. num (j);
                                if (n >= sizeA1)
                                        continue;
                                phiColumn. add (M_A1. getcol (n), one);
                        }

                        // decode the resulting chain and put it in phi
                        int_t sizePhiColumn = phiColumn. size ();
                        for (int j = 0; j < sizePhiColumn; ++ j)
                        {
                                int_t n = phiColumn. num (j);
                                phi. add (cells [q - 1] [i],
                                        cells [q] [n]);
                        }
                }
        }

        // show timing information
        sout << "Homology gvf composed from the SNF in " << gvfTime << ".\n";

        // show information on the total computation time of this routine
        sout << "Homology gvf computed in " << compTime << ".\n";

        return;
} /* homologyGVF3 */


#endif // _CHAINCON_HOMGVF3_H_