Finding the largest common matrix divisor in MATLAB

Question

Im looking for a way to separate some elements of the matrix with its lowest common divisor.

for example, I have vectors

[0,0,0; 2,4,2;-2,0,8] 

I can say that the lowest common factor is 2, so the matrix after division will be

 [0,0,0;1,2,1;-1,0,4] 

What is a built-in method that can calculate this?

Thank you in advance

ps I personally do not like the use of loops for this calculation, it seems that the calculations have a built-in calculation that can perform the separation of matrix elements.

Answer 1

Since you don't like loops, what about recursive functions?

 iif = @(varargin) varargin{2 * find([varargin{1:2:end}], 1, 'first')}(); gcdrec=@ (v,gcdr) iif(length(v)==1,v, ... v(1)==1,1, ... length(v)==2,@()gcd(v(1),v(2)), ... true,@()gcdr([gcd(v(1),v(2)),v(3:end)],gcdr)); mygcd=@ (v)gcdrec(v(:)',gcdrec); A=[0,0,0; 2,4,2;-2,0,8]; divisor=mygcd(A); A=A/divisor; 

The first iif function will define an inline conditional construct. This allows you to define the gcdrec recursive function to find the largest common divisor of your array. This iif works as follows: it checks if the first argument is true , if it is, then it returns the second argument. Otherwise, it checks the third argument, and if it is true , then it returns the fourth, etc. You need to protect recursive functions, and sometimes other quantities appearing inside it, with @() , otherwise you may get errors.

Using iif , the recursive gcdrec function works as follows:

• if the input vector is a scalar, it returns it
• else, if the first component of the vector is 1, there is no way to restore, so it returns 1 (allows you to quickly return large matrices)
• else, if the input vector is 2, it returns the greatest common factor through gcd
• else he calls himself an abbreviated vector in which the first two elements are replaced by their largest common divisor.

The mygcd function is just an interface for convenience.

It should be pretty fast, and I think that only the depth of the recursion can be a problem for very big problems. I did a quick time check to compare with the cyclic version of @Adriaan using A=randi(100,N,N)-50 , with N=100 , N=1000 and N=5000 and tic / toc .

• N=100 :
  • looping 0.008 seconds
  • recursive 0.002 seconds
• N=1000 :
  • 0.46 second cycle
  • recursive 0.04 seconds
• N=5000 :
  • 11.8 seconds cycle
  • recursive 0.6 seconds

Refresh . Interestingly, the only reason I did not exceed the recursion limit (500 by default) is because my data did not have a common divisor. By setting a random matrix and doubling it, it will lead to reaching the recursion limit already for N=100 . Therefore, for large matrices this will not work. Again, for small matrices, @Adriaan's solution is fine.

I also tried to rewrite it to half the input vector at each recursive step: this really solves the recursion restriction problem, but it is very slow (2 seconds for N=100 , 261 seconds for N=1000 ). Somewhere somewhere there may be a middle place where the size of the matrix is ​​large (ish) and the execution time is not so bad, but I have not found it yet.

Answer 2

  A = [0,0,0; 2,4,2;-2,0,8]; B = 1; kk = max(abs(A(:))); % start at the end while B~=0 && kk>=0 tmp = mod(A,kk); B = sum(tmp(:)); kk = kk - 1; end kk = kk+1; 

This is probably not the fastest way, but for now it will be done. What I did here is to initialize some counter B to keep the sum of all the elements in your matrix after taking mod . kk is just a counter that runs through integers. mod(A,kk) computes the modulus after division for each element in A That way, if all of your elements are completely divisible by 2, it will return 0 for each element. sum(tmp(:)) then returns one column from the modular matrix, which is summed to get a certain number. If and only if this number is 0, then there is a common factor, since then all elements from A completely divisible by kk . Once this happens, your loop will stop and your common divisor is the number in kk . Since kk decreases every count, this is actually one value too low, so it is added.

Note. I just edited a loop to run backwards, since you are looking for the largest CD, not the smallest CD. If you had a matrix like [4,8;16,8] , it would stop at 2 , not 4 . I apologize for this, now it works, although other solutions here are much faster.

Finally, separation matrices can be done as follows:

 divided_matrix = A/kk; 

Answer 3

I agree, I don't like the loops either! Let them kill them -

 unqA = unique(abs(A(A~=0))).'; %//' col_extent = [2:max(unqA)]'; %//' B = repmat(col_extent,1,numel(unqA)); B(bsxfun(@gt,col_extent,unqA)) = 0; divisor = find(all(bsxfun(@times,bsxfun(@rem,unqA,B)==0,B),2),1,'first'); if isempty(divisor) out = A; else out = A/divisor; end 

Run Examples

Case No. 1:

 A = 0 0 0 2 4 2 -2 0 8 divisor = 2 out = 0 0 0 1 2 1 -1 0 4 

Case No. 2:

 A = 0 3 0 5 7 6 -5 0 21 divisor = 1 out = 0 3 0 5 7 6 -5 0 21 

Answer 4

Here is another approach. Let A be your input array.

• Get non-zero values ​​of A and accept their absolute value. Call the resulting vector B
• Check each number from 1 to max(B) and check if it divides all the entries of B (that is, if the remainder of the division is zero).
• Take the highest number.

code:

 A = [0,0,0; 2,4,2;-2,0,8]; %// data B = nonzeros(abs(A)); %// step 1 t = all(bsxfun(@mod, B, 1:max(B))==0, 1); %// step 2 result = find(t, 1, 'last'); %// step 3 

Answer 5

For the answer above, would it be more efficient to change max (B) to min (B)?