genericmatrix.py

著名的ldpc编解码的资料及源代码

            for j in range(other.cols):
                result.data[i][j] = reduce(self.add,
                                           map(self.mul,self.data[i],
                                               other.GetColumn(j)))
        return result

    def __add__(self,other):
        if (self.cols != other.rows):
            raise ValueError, "dimension mismatch"
        result = self.MakeSimilarMatrix(size=self.Size(),fillMode='z')
        for i in range(self.rows):
            for j in range(other.cols):
                result.data[i][j] = self.add(self.data[i][j],other.data[i][j])
        return result
    
    def __sub__(self,other):
        if (self.cols != other.cols or self.rows != other.rows):
            raise ValueError, "dimension mismatch"
        result = self.MakeSimilarMatrix(size=self.Size(),fillMode='z')
        for i in range(self.rows):
            for j in range(other.cols):
                result.data[i][j] = self.sub(self.data[i][j],
                                             other.data[i][j])
        return result

    def __setitem__ (self, (x,y), data):
        "__setitem__((x,y),data) sets item row x and column y to data."
        self.data[x][y] = data

    def __getitem__ (self, (x,y)):
        "__getitem__((x,y)) gets item at row x and column y."
        return self.data[x][y]

    def Size (self):
        "returns (rows, columns)"
        return (len(self.data), len(self.data[0]))

    def SetRow(self,r,result):
        "SetRow(r,result) sets row r to result."
        
        assert len(result) == self.cols, ('Wrong # columns in row: ' +
                                          'expected ' + `self.cols` + ', got '
                                          + `len(result)`)
        self.data[r] = list(result)

    def GetRow(self,r):
        "GetRow(r) returns a copy of row r."
        return list(self.data[r])

    def GetColumn(self,c):
        "GetColumn(c) returns a copy of column c."
        if (c >= self.cols):
            raise ValueError, 'matrix does not have that many columns'
        result = []
        for r in self.data:
            result.append(r[c])
        return result

    def Transpose(self):
        oldData = self.data
        self.data = []
        for r in range(self.cols):
            self.data.append([])
            for c in range(self.rows):
                self.data[r].append(oldData[c][r])
        rows = self.rows
        self.rows = self.cols
        self.cols = rows

    def Copy(self):
        result = self.MakeSimilarMatrix(size=self.Size(),fillMode='e')

        for r in self.data:
            result.data.append(list(r))
        return result

    def SubMatrix(self,rowStart,rowEnd,colStart=0,colEnd=None):
        """
        SubMatrix(self,rowStart,rowEnd,colStart,colEnd)
        Create and return a sub matrix containg rows
        rowStart through rowEnd (inclusive) and columns
        colStart through colEnd (inclusive).
        """
        if (not colEnd):
            colEnd = self.cols-1
        if (rowEnd >= self.rows):
            raise ValueError, 'rowEnd too big: rowEnd >= self.rows'
        result = self.MakeSimilarMatrix((rowEnd-rowStart+1,colEnd-colStart+1),
                                        'e')

        for i in range(rowStart,rowEnd+1):
            result.data.append(list(self.data[i][colStart:(colEnd+1)]))

        return result
 
    def UnSubMatrix(self,rowStart,rowEnd,colStart,colEnd):
        """
        UnSubMatrix(self,rowStart,rowEnd,colStart,colEnd)
        Create and return a sub matrix containg everything except
        rows rowStart through rowEnd (inclusive) 
        and columns colStart through colEnd (inclusive).
        """
        result = self.MakeSimilarMatrix((self.rows-(rowEnd-rowStart),
                                         self.cols-(colEnd-colStart)),'e')

        for i in range(0,rowStart) + range(rowEnd,self.rows):
            result.data.append(list(self.data[i][0:colStart] +
                                    self.data[i][colEnd:]))

        return result


    def SwapRows(self,i,j):
        temp = list(self.data[i])
        self.data[i] = list(self.data[j])
        self.data[j] = temp

    def MulRow(self,r,m,start=0):
        """
        Function: MulRow(r,m,start=0)
        Multiply row r by m starting at optional column start (default 0).
        """
        row = self.data[r]
        for i in range(start,self.cols):
            row[i] = self.mul(row[i],m)

    def AddRow(self,i,j):
        """
        Add row i to row j.
        """
        self.data[j] = map(self.add,self.data[i],self.data[j])

    def AddCol(self,i,j):
        """
        Add column i to column j.
        """
        for r in range(self.rows):
            self.data[r][j] = self.add(self.data[r][i],self.data[r][j])

    def MulAddRow(self,m,i,j):
        """
        Multiply row i by m and add to row j.
        """
        self.data[j] = map(self.add,
                           map(self.mul,[m]*self.cols,self.data[i]),
                           self.data[j])

    def LeftMulColumnVec(self,colVec):
        """
        Function:       LeftMulColumnVec(c)
        Purpose:        Compute the result of self * c.
        Description:    This function taks as input a list c,
                        computes the desired result and returns it
                        as a list.  This is sometimes more convenient
                        than constructed a new GenericMatrix to represent
                        c, computing the result and extracting c to a list.
        """
        if (self.cols != len(colVec)):
            raise ValueError, 'dimension mismatch'
        result = range(self.rows)
        for r in range(self.rows):
            result[r] = reduce(self.add,map(self.mul,self.data[r],colVec))
        return result

    def FindRowLeader(self,startRow,c):
        for r in range(startRow,self.rows):
            if (not self.eq(self.zeroElement,self.data[r][c])):
                return r
        return -1

    def FindColLeader(self,r,startCol):
        for c in range(startCol,self.cols):
            if (not self.equalsZero(self.data[r][c])):
                return c
        return -1    

    def PartialLowerGaussElim(self,rowIndex,colIndex,resultInv):
        """
        Function: PartialLowerGaussElim(rowIndex,colIndex,resultInv)
        
        This function does partial Gaussian elimination on the part of
        the matrix on and below the main diagonal starting from
        rowIndex.  In addition to modifying self, this function
        applies the required elmentary row operations to the input
        matrix resultInv.

        By partial, what we mean is that if this function encounters
        an element on the diagonal which is 0, it stops and returns
        the corresponding rowIndex.  The caller can then permute
        self or apply some other operation to eliminate the zero
        and recall PartialLowerGaussElim.
        
        This function is meant to be combined with UpperInverse
        to compute inverses and LU decompositions.
        """

        lastRow = self.rows-1
        while (rowIndex < lastRow):
            if (colIndex >= self.cols):
                return (rowIndex, colIndex)
            if (self.eq(self.zeroElement,self.data[rowIndex][colIndex])):
                # self[rowIndex,colIndex] = 0 so quit.
                return (rowIndex, colIndex)
            divisor = self.div(self.identityElement,
                               self.data[rowIndex][colIndex])
            for k in range(rowIndex+1,self.rows):
                nextTerm = self.data[k][colIndex]
                if (self.zeroElement != nextTerm):
                    multiple = self.mul(divisor,self.sub(self.zeroElement,
                                                         nextTerm))
                    self.MulAddRow(multiple,rowIndex,k)
                    resultInv.MulAddRow(multiple,rowIndex,k)
            rowIndex = rowIndex + 1
            colIndex = colIndex + 1
        return (rowIndex, colIndex)

    def LowerGaussianElim(self,resultInv=''):
        """
        Function:       LowerGaussianElim(r)
        Purpose:        Perform Gaussian elimination on self to eliminate
                        all terms below the diagonal.
        Description:    This method modifies self via Gaussian elimination
                        and applies the elementary row operations used in
                        this transformation to the input matrix, r
                        (if one is provided, otherwise a matrix with
                         identity elements on the main diagonal is
                         created to serve the role of r).

                        Thus if the input, r, is an identity matrix, after
                        the call it will represent the transformation
                        made to perform Gaussian elimination.

                        The matrix r is returned.
        """
        if (resultInv == ''):
            resultInv = self.MakeSimilarMatrix(self.Size(),'i')
            
        (rowIndex,colIndex) = (0,0)
        lastRow = min(self.rows - 1,self.cols)
        lastCol = self.cols - 1
        while( rowIndex < lastRow and colIndex < lastCol):
            leader = self.FindRowLeader(rowIndex,colIndex)
            if (leader < 0):
                colIndex = colIndex + 1
                continue
            if (leader != rowIndex):
                resultInv.AddRow(leader,rowIndex)
                self.AddRow(leader,rowIndex)
            (rowIndex,colIndex) = (
                self.PartialLowerGaussElim(rowIndex,colIndex,resultInv))
        return resultInv

    def UpperInverse(self,resultInv=''):
        """
        Function: UpperInverse(resultInv)
        
        Assumes that self is an upper triangular matrix like

          [a b c ... ]
          [0 d e ... ]
          [0 0 f ... ]
          [.     .   ]
          [.      .  ]
          [.       . ]

        and performs Gaussian elimination to transform self into
        the identity matrix.  The required elementary row operations
        are applied to the matrix resultInv passed as input.  For
        example, if the identity matrix is passed as input, then the
        value returned is the inverse of self before the function
        was called.

        If no matrix, resultInv, is provided as input then one is
        created with identity elements along the main diagonal.
        In either case, resultInv is returned as output.
        """
        if (resultInv == ''):
            resultInv = self.MakeSimilarMatrix(self.Size(),'i')
        lastCol = min(self.rows,self.cols)
        for colIndex in range(0,lastCol):
            if (self.zeroElement == self.data[colIndex][colIndex]):
                raise ValueError, 'matrix not invertible'
            divisor = self.div(self.identityElement,
                               self.data[colIndex][colIndex])
            if (self.identityElement != divisor):
                self.MulRow(colIndex,divisor,colIndex)
                resultInv.MulRow(colIndex,divisor)
            for rowToElim in range(0,colIndex):
                multiple = self.sub(self.zeroElement,
                                    self.data[rowToElim][colIndex])
                self.MulAddRow(multiple,colIndex,rowToElim)
                resultInv.MulAddRow(multiple,colIndex,rowToElim)
        return resultInv
    
    def Inverse(self):
        """
        Function:       Inverse
        Description:    Returns the inverse of self without modifying
                        self.  An exception is raised if the matrix