3

I am trying to implement an algorithm requiring matrix multiplication. I know I can program this in the rudimentary way similar to doing the process by hand, but I am worried about the computational costs associated with this.

In solidity, the "matrix" would just be a two-dimensional array or even just a vector.

Does anyone know of an existing implementation of matrix multiplication in solidity? I want to make sure I do this efficiently and am wondering if anyone else has established a good way of doing it. I am unable to find any library or posts on the subject.

Thanks in advance.

  • You might have to go with a counter-intuitive approach to complete it with O(1) complexity. How big is the matrix? How often does it change? What makes it change? What is it for? A general-purpose approach is probably out of the question, so more insight into the specific requirements might help pinpoint a suitable method for you. – Rob Hitchens - B9lab Jun 10 at 15:05
  • Thanks, the matrices multiplied will not be huge. Say, 10x10 or less. Matrix multiplication will be done very frequently. In particular, the multiplication being done will be a square matrix by a vector. The square matrix will not change, but the vector will change every time. I am doing this to implement a decentralized consensus algorithm on the blockchain, where each node queries the smart contract to receive their next state. – user51707 Jun 10 at 15:23
  • That's encouraging. Writes are considerably more expensive than reads so it is good news that the 10x10 structure is static. Where does the vector come from? How does it evolve? I imagine it is computed deterministically somehow? – Rob Hitchens - B9lab Jun 10 at 15:31
  • Yes, it is. I believe I have a "good enough" solution that I will work with for now as long as I know the array sizes. Thank you for your answer and help. – user51707 Jun 10 at 16:01
0

This simple method is what I will use for now as long as I know the dimensions of the matrices. Thanks.

function mat3Mult(uint[3][3] mat1, uint[3][3] mat2) private returns (uint[3][3]) { // multiplies 3x3 matrix with 3x3 matrix
        uint r1 = mat1.length; // rows of mat1
        uint c1 = mat1[0].length; // columns of mat1
        uint c2 = mat2[0].length; // columns of mat2

        uint[3][3] memory result; 

        for(uint i = 0; i < r1; ++i) {
            for(uint j = 0; j < c2; ++j) {
                for(uint k = 0; k < c1; ++k) {
                    result[i][j] += mat1[i][k] * mat2[k][j];
                }
            }
        }

        return(result);
    }

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.