在MATLAB中找到矩阵的最大公约数

Question

我正在寻找一种方法来划分具有最低公约数的某些矩阵元素.

例如,我有矢量

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

我可以告诉最低公约数是2,所以除法后的矩阵将是

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

什么是内置方法可以计算这个？

提前致谢

ps我个人不喜欢使用循环进行此计算,似乎内置计算可以执行矩阵元素划分.

Answer 1

既然你不喜欢循环,那么递归函数呢？

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;

第一个函数iif将定义内联条件结构.这允许定义递归函数,gcdrec以找到数组的最大公约数.这样的iif工作原理如下:它测试第一个参数是否为true,如果是,则返回第二个参数.否则它会测试第三个参数,如果是 true,则返回第四个,依此类推.您需要保护递归函数,有时还要保护其中出现的其他数量@(),否则可能会出错.

使用iif递归函数的gcdrec工作方式如下:

• 如果输入向量是标量,则返回它
• 否则,如果向量的第一个分量为1,则没有机会恢复,因此它返回1(允许快速返回大型矩阵)
• 否则,如果输入向量的长度为2,则返回最大公约数via gcd
• 否则它会使用缩短的向量调用自身,其中前两个元素被其最大公约数替换.

该功能mygcd只是方便的前端.

应该非常快,我想只有递归深度可能是一个非常大的问题的问题.我做了一个快速定时检查与@Adriaan的循环版本进行比较,使用A=randi(100,N,N)-50,用N=100,N=1000以及N=5000和tic/ toc.

1. N=100:
   • 循环0.008秒
   • 递归0.002秒
2. N=1000:
   • 循环0.46秒
   • 递归0.04秒
3. N=5000:
   • 循环11.8秒
   • 递归0.6秒

更新:有趣的是,我没有绊倒递归限制(默认情况下为500)的唯一原因是我的数据没有公共除数.设置随机矩阵并将其加倍将导致达到递归限制N=100.因此对于大型矩阵,这是行不通的.再说一次,对于小矩阵,@ Adriaan的解决方案非常好.

我还尝试在每个递归步骤中将其重写为输入向量的一半:这确实解决了递归限制问题,但它非常慢(2秒N=100,261秒N=1000).某处可能存在中间地带,矩阵大小很大(ish),运行时间并不差,但我还没有找到它.

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;

这可能不是最快的方式,但它现在可以做到.我在这里做的是初始化一些计数器,B以便在获取之后存储矩阵中所有元素的总和mod.这kk只是一个贯穿整数的计数器.mod(A,kk)计算每个元素的除法后的模数A.因此,如果所有元素都可以被2整除,则每个元素将返回0.sum(tmp(:))然后从模数矩阵中生成一个单独的列,将其相加以获得一些数字.当且仅当该数字为0时,存在公约数,因为那时所有元素A都可以被整除kk.一旦发生这种情况,你的循环就会停止,你的公约数就是kk.以来kk 每减少一个值,它实际上是一个值太低,因此增加了一个.

注意:我刚编辑循环以向后运行, 因为您正在寻找最大的CD,而不是最小的CD.如果你有一个矩阵就像[4,8;16,8]它会停止2,而不是4.对此表示抱歉,现在这种方法有效,尽管这里的其他解决方案都要快得多.

最后,划分矩阵可以这样做:

divided_matrix = A/kk;