Skip to content
Snippets Groups Projects
lineardependency.go 2.95 KiB
Newer Older
  • Learn to ignore specific revisions
  • package resolver
    
    import (
    	"fmt"
    
    	"git.noc.ruhr-uni-bochum.de/danieljankowski/gomatrix"
    )
    
    // LinearDependenciesInGauss tries to resolve linear dependencies in the gaussian
    // elimination.
    //
    // This function is used in order to try to resolve linear dependencies while
    // using the function PartialGaussianWithLinearChecking as linearCheck-function.
    func LinearDependenciesInGauss(
    	f *gomatrix.F2,
    
    	startRow int,
    	startCol int,
    	stopRow int,
    	stopCol int,
    	pivotBit int,
    
    ) (*gomatrix.F2, *gomatrix.F2, error) {
    
    	// resolve the linear dependency
    
    	permutationMatrix, err := resolveWithOptimizedAlgorithm(
    
    		startRow,
    		startCol,
    		stopRow,
    		stopCol,
    		pivotBit,
    	)
    
    	// if an error occured...
    	if err != nil {
    		// ...return it
    
    	// apply the previous operations on the new row, with iterating through
    	// the columns 'til the pivot bit is reached
    
    	for i := startCol; i < pivotBit; i++ {
    
    		// if the column is zero...
    
    		if f.Rows[pivotBit-startCol].Bit(i) == uint(0) {
    
    			// ...skip to the next column
    
    		// remove the 1 with a xor operation with the relating row
    
    		f.Rows[startRow+pivotBit-startCol].Xor(
    			f.Rows[startRow+pivotBit-startCol],
    
    		gaussMatrix.Rows[startRow+pivotBit-startCol].Xor(
    			gaussMatrix.Rows[startRow+pivotBit-startCol],
    			gaussMatrix.Rows[startRow+i-startCol],
    
    	return gaussMatrix, permutationMatrix, nil
    
    // resolveWithOptimizedAlgorithm tries to resolve the dependency with finding
    // an appropriate value that can be swapped right into the correct position
    // without destroying the already processed rows and columns.
    func resolveWithOptimizedAlgorithm(
    
    	startRow int,
    	startCol int,
    	stopRow int,
    	stopCol int,
    	pivotBit int,
    
    	// iterate through the rows
    	for rowIndex := 0; rowIndex < f.N; rowIndex++ {
    		// if the rowindex points on to the already processed rows...
    		if rowIndex >= startRow && rowIndex <= startRow+pivotBit-startCol {
    			// ...skip it
    
    		// iterate through the columns
    		for colIndex := 0; colIndex < f.M; colIndex++ {
    			// if the colindex points on to the already processed rows...
    			if colIndex >= startCol && colIndex < pivotBit {
    				// ...skip it
    				continue
    			}
    
    			// get the value at the current index
    			bit, err := f.At(rowIndex, colIndex)
    
    			// if an error occured or the bit is 0...
    			if err != nil || bit == 0 {
    				// ...skip it
    				continue
    			}
    
    			// swap the value into the right place
    			f.SwapRows(rowIndex, startRow+pivotBit-startCol)
    			f.SwapCols(colIndex, pivotBit)
    
    
    			// swap the rows in the permutation matrix
    			permutationMatrix.SwapRows(rowIndex, startRow+pivotBit-startCol)
    			permutationMatrix.SwapCols(colIndex, pivotBit)
    
    
    			// return success
    
    	return nil, fmt.Errorf("cannot resolve dependency")