How can I raise a sparse triangular matrix stored in a nested dictionary to the 2nd power?-CodePudding

I have a sparse triangular matrix that I need to raise to the 2nd power. The problem is, one of the requirements is that the matrix is stored as a nested dictionary (I need to create a python implementation), and so the standard functions from numpy do not apply. (I know this way of storing a matrix is probably overkill, but this is for a university course)

Below is how I've implemented the creation of the matrix itself (rare is the equivalent to sparse here):

    def __init__(self, *matrix):
        self.rare_values = dict()
        if len(matrix) > 0:
            for i, line in enumerate(matrix):
                if i == 0:
                    self.n = line
                    continue
                value = line[0]
                i = line[1]
                j = line[2]
                if j > i:

                    i = line[2]
                    j = line[1]
                if i in self.rare_values.keys():
                    if j in self.rare_values[i].keys():
                        self.rare_values[i][j]  = value
                    else:
                        dict_column = {j: value}
                        self.rare_values[i].update(dict_column)
                else:
                    dict_line = {i: {j: value}}
                    self.rare_values.update(dict_line)

My question is, would it be possible to implement an algorithm to raise such a matrix to the 2nd power? If so, I would be more than thankful if you could provide a pseudocode or minimalist explanation as to how I may go about it.

Thank you!

CodePudding user response：

The code you provided can be significantly reduced to something like:

class Sparse:
    def __init__(self, n=None, *matrix):
        self.rare_values = dict()
        self.n = n
        for line in matrix:
            value, *indices = line
            c,r = sorted(indices)
            # Personally, here I would have instead used
            #   r,c = sorted(indices, reverse=True)
            # as (r,c) order seems more common, but it's no big deal.
            self.rare_values.setdefault(r, {})[c] = value

This produces the same structure as your __init__ method, just more clearly (IMO).

From there, squaring each of the values is as simple as iterating over the dict-of-dicts, e.g. using nested for loops iterating over .items():

    def square(self):
        for (r,row) in self.rare_values.items():
            for (c,val) in row.items():
                self.rare_values[r][c] = val ** 2

Example:

class Sparse:
    def __init__(self, n=None, *matrix):
        self.rare_values = dict()
        self.n = n
        for line in matrix:
            value, *indices = line
            c,r = sorted(indices)
            self.rare_values.setdefault(r, {})[c] = value

    def square(self):
        for (r,row) in self.rare_values.items():
            for (c,val) in row.items():
                self.rare_values[r][c] = val ** 2

s = Sparse(3, (0,0,0), (2,1,1), (4,0,2), (6,2,3), (8,0,4))
print(s.rare_values)  # {0: {0: 0}, 1: {1: 2}, 2: {0: 4}, 3: {2: 6}, 4: {0: 8}}
s.square()
print(s.rare_values)  # {0: {0: 0}, 1: {1: 4}, 2: {0: 16}, 3: {2: 36}, 4: {0: 64}}

Follow-up from comments

The following example shows how you might raise the matrix to a power (not the element-wise operation I showed above).

Note this code changes some things from your version and my original version. It accepts items in (r,c,v) order and doesn't attempt to "normalize" the indices like you do to force a triangular matrix.

If you want that behavior you'll have to edit this version to re-add that back.

class Sparse:
    def __init__(self, n=None, entries=None):
        self.matrix = dict()
        self.n = n
        for (r,c,v) in (entries or []):
            self.set(r, c, v)

    def set(self, r, c, v):
        self.matrix.setdefault(r, {})[c] = v

    def get(self, r, c):
        return self.matrix.get(r, {}).get(c, 0)

    def square_matrix(self):
        result = Sparse(self.n)
        for r in range(self.n):
            for c in range(self.n):
                val = sum(self.get(r,i) * self.get(i,c) for i in range(self.n))
                result.set(r, c, val)

        return result

sparse = Sparse(2, [
    (0,0,1), (0,1,2),
    (1,0,3), (1,1,4),
])
print(sparse.matrix)   # {0: {0: 1, 1: 2}, 1: {0: 3, 1: 4}}
#                        = [[1 2]
#                           [3 4]]
result = sparse.square_matrix()
print(result.matrix)   # {0: {0: 7, 1: 10}, 1: {0: 15, 1: 22}}
#                        = [[ 7 10]
#                           [15 20]]