top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Best way to find min of square of difference sub-matrices of a matrix to another matrix

0 votes
595 views

suppose

A(n,m) = 
1 2 3         
4 5 6                            
7 8 9

and 

B(p, q) = 
1 1
1 1

What is best method to find min of square of difference of sub-matrices of A and B e.g.

sub-matrices of A =

1 2    |     2 3   |    4 5    |   5 6
3 4    |     5 6   |    7 8    |   8 9

Difference of first sub-matrix of A with B =

(1-1)  (2-1)    = |     0 1
(3-1)  (4-1)      |     2 3

sum of square of elements = 0*0 + 1*1 + 2*2 + 3*3 = 14

similar steps for other sub-matrices of A

Please suggest looking for an alternate method or algorithm which has time complexity less than O(n*m*p*q)

posted Jul 4, 2014 by Pankaj Agarwal

Looking for an answer?  Promote on:
Facebook Share Button Twitter Share Button LinkedIn Share Button
I see this as a three different problems
1. one is finding the list of submatrix
And for each of sub matrix
2. Find the sum of squares of each elements
3. Find the diff of individual difference between submatrix and matrix B.

unfortunately mine is also o(n^4) so not submitting my solution. If you know something better please answer (I like to know)

Similar Questions
+4 votes

Given a binary matrix, find out the maximum size square sub-matrix with all 1 s, Recusively

For example, consider the below binary matrix.
(Source:- geeksforgeeks

   0  1  1  0  1 
   1  1  0  1  0 
   0  1  1  1  0
   1  1  1  1  0
   1  1  1  1  1
   0  0  0  0  0

The maximum square sub-matrix with all set bits is

1  1  1
1  1  1
1  1  1

As we know it's general solution is with DP, but here i am interested in Recursive Approach

0 votes
for(i=0;i<n;i++)
  for(j=0;j<n;j++)
     for(k=0;k<n;k++)
        C[i][j]+=A[i][k]*B[k][j];

In this algorithm, there are 6 combinations of loops : the one given above is ijk. The others are ikj,jki,jik,kij and kji. Which one executes the fastest and why?

...