Is it faster to use the mobius_function_matrix?

[Theo Belaire]

Is it faster to switch to using the mobius_function_matrix if I only want the intervals starting from zero?

I'm also confused about what it means by the linear extension.

The part of my code in question is

    F = [] 

    for i in range(M.rank()+1): 

        F.extend(M.flats(i))

    P = Poset((F, lambda x, y: x <= y)) 

    nu = {}

    for i in range(M.rank() + 1):

        for e in M.flats(i):

            nu[e] = P.mobius_function(P[0], e)

    print nu

    print P.mobius_function_matrix()

prints:

{frozenset([2]): -1, frozenset([0, 1, 2]): 2, frozenset([]): 1, frozenset([0]): -1, frozenset([1]): -1}

[ 1 -1 -1 -1  2]

[ 0  1  0  0 -1]

[ 0  0  1  0 -1]

[ 0  0  0  1 -1]

[ 0  0  0  0  1]

Don't worry about flats or M, it has to do with matroids.

I was wondering if it would be faster to switch to using the mobius_function_matrix, and how do I index into it properly?  What's the mapping from my sets to the indices?

Also, the relevant code from sage:

    def mobius_function(self,i,j): # dumb algorithm

        r"""

        Returns the value of the M\"obius function of the poset

        on the elements ``i`` and ``j``.

        EXAMPLES::

            sage: P = Poset([[1,2,3],[4],[4],[4],[]])

            sage: H = P._hasse_diagram

            sage: H.mobius_function(0,4)

            2

            sage: for u,v in P.cover_relations_iterator():

            ...    if P.mobius_function(u,v) != -1:

            ...        print "Bug in mobius_function!"

        """

        try:

            return self._mobius_function_values[(i,j)]

        except AttributeError:

            self._mobius_function_values = {}

            return self.mobius_function(i,j)

        except KeyError:

            if i == j:

                self._mobius_function_values[(i,j)] = 1

            elif i > j:

                self._mobius_function_values[(i,j)] = 0

            else:

                ci = self.closed_interval(i,j)

                if len(ci) == 0:

                    self._mobius_function_values[(i,j)] = 0

                else:

                    self._mobius_function_values[(i,j)] = \

                     -sum([self.mobius_function(i,k) for k in ci[:-1]])

        return self._mobius_function_values[(i,j)]

    def mobius_function_matrix(self):

        r"""

        Returns the matrix of the mobius function of this poset

        This returns the sparse matrix over ZZ whose ``(x, y)`` entry

        is the value of the M\"obius function of ``self`` evaluated on

        ``x`` and ``y``, and redefines :meth:`mobius_function` to use

        it

        .. note::

            The result is cached in ``self._mobius_function_matrix``.

        EXAMPLES::

            sage: from sage.combinat.posets.hasse_diagram import HasseDiagram

            sage: H = HasseDiagram({0:[1,3,2],1:[4],2:[4,5,6],3:[6],4:[7],5:[7],6:[7],7:[]})

            sage: H.mobius_function_matrix()

            [ 1 -1 -1 -1  1  0  1  0]

            [ 0  1  0  0 -1  0  0  0]

            [ 0  0  1  0 -1 -1 -1  2]

            [ 0  0  0  1  0  0 -1  0]

            [ 0  0  0  0  1  0  0 -1]

            [ 0  0  0  0  0  1  0 -1]

            [ 0  0  0  0  0  0  1 -1]

            [ 0  0  0  0  0  0  0  1]

        TESTS::

            sage: H.mobius_function_matrix().is_immutable()

            True

            sage: hasattr(H,'_mobius_function_matrix')

            True

            sage: H.mobius_function == H._mobius_function_from_matrix

            True

        """

        if not hasattr(self,'_mobius_function_matrix'):

            self._mobius_function_matrix = self.lequal_matrix().inverse().change_ring(ZZ)

            self._mobius_function_matrix.set_immutable()

            self.mobius_function = self._mobius_function_from_matrix

        return self._mobius_function_matrix