0

I am trying to write a solidity contract to compute Matrix determinant. I am following the C++ implementation from here: https://www.tutorialspoint.com/cplusplus-program-to-compute-determinant-of-a-matrix

The following code works fine up to a square matrix of size 5. But when the size increases it fails to compute. I have also increased the gas limit in Remix and tried to run but still, it fails. (Also tried to run using Web3 provider - Ganache with an increased gas limit, but ganache crashed/failed to run.) I am looking to implement it for Matrix sizes 12 to 15.

Any help is highly appreciated. Thanks.

I have attached my code below:

contract Determinant {
  uint [5][5] public matA = [[1,1,2,1,2],[3,0,0,5,4],[2,1,4,3,1],[1,0,5,0,7],[4,2,5,4,3]];
  uint public matrix_order;
  int256 public output = 0;
  uint [5] public temp_output;

function compute () public {
    matrix_order = matA.length;
    output = determinantOfMatrix(matA, matrix_order);
}

function determinantOfMatrix (uint[5][5] memory mat1, uint _order) private returns (int256) {
    uint [5][5] memory submatrix;
    int256 det = 0;
    uint256 sign = 1;
    int256 result;

    if (_order == 2)
        return int256((mat1[0][0] * mat1[1][1]) - (mat1[1][0] * mat1[0][1]));
    else {
        for (uint x = 0; x < _order; x++){
            uint subi = 0;
            for (uint i = 1; i< _order; i++){
                uint subj = 0;
                for(uint j = 0; j<_order; j++){
                    if (j != x){
                        submatrix[subi][subj] = mat1[i][j];
                        subj++;
                    }
                }
                subi++;
            }
            result = int256((-sign) ** x);
            temp_output[x] = mat1[0][x] * uint(determinantOfMatrix (submatrix, _order - 1 ));
            det = det + result * int256(temp_output[x]);
        }
        return det;
    }
}    

}

  • What error do you get? Solidity is not ideal to do intensive mathematics or any other complex task. Some resources like memory is very constrained. – Ismael Apr 22 at 18:11
  • 1
    Last note - you are not checking for overflows (as a result of + or *) and underflows (as a result of -) anywhere in your code. That by itself could lead to incorrect results very easily. – goodvibration Apr 22 at 19:51
  • 1
    So you should most definitely use (-sign) ** x and not -sign ** x!!! – goodvibration Apr 23 at 5:31
  • 1
    After improving some of your code, I too haven't been able to run it for more than 6 without reverting. For 6, I always get zero so I suspect that there's a problem with that as well (though perhaps it is a purely computational problem, for example, due to overflows or underflows as I've mentioned above). In short, you'll need to change your implementation from recursive to iterative – goodvibration Apr 23 at 5:49
  • 1
    @NB18 In general I'd recommend to avoid any intensive computation, and if possible use smart contracts to verify the result. Obviously it depends on the problem you are trying to solve. Possible approaches I will try in this case: receive determinant as parameter, require diagonal matrix, LU decomposed matrix. – Ismael Apr 23 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.