How can I speed up gfmul for large fields?

5 次查看（过去 30 天）
Ethan Duckworth
Ethan Duckworth 2022-3-11
评论： Ethan Duckworth 2024-2-13
I would like to do some arithmetic, like find inverses and do multiplication in the Galois field GF(29^4). The commands gfmul works well for this task for GF(29^3):
p=29;
m=3;
conway = [27 2 0 1]; % conway poly
field = gftuple([-1:p^m-2]',conway,p); % 7072801x4 double
g_e = 28*29^2+29; % exponential form of test case poly
unit=0; % exponential form of unit
tic
ginv_e = gfdiv(unit,g_e,field); % calculate g inverse
toc % 0.29s on my machine
tic
gfmul(ginv_e,g_e,field) % test: answer should be 0
toc % 0.37s on my machine
But when I try the same thing for p=29 and m=3 it is MUCH slower
p=29;
m=4;
conway = [2 15 2 0 1];
field = gftuple([-1:p^m-2]',conway,p);
g_e = 28*29^3+29^2;
unit=0;
tic
ginv_e = gfdiv(0,g_e,field);
toc % 7.4s on my machine
tic
gfmul(ginv_e,g_e,field)
toc % *** 344s on my machine!! ****
% try to mult using coefficients and convolution
g_c = gftuple(g_e,conway,p) % coefficient form of g
ginv_c = gftuple(ginv_e,conway,p)
tic
prod = gfconv(ginv_c,g_c,p); % convolution mod p
gftuple(prod,conway,p) % reduce mod conway poly, answer should be 1 0 0 0
toc % 1.2s on my machine
  1. Any way to get "gmul(ginv_e,g_e,field)" to go faster? Is it something about the size of the "field" array and how Matlab moves that around in memory?
  2. Ideally I'd get gmul to go faster, but there are two work arounds (a) I can perform an equivalent calculation using gfconv, and it's 1.2s. (b) I can work all the way around and use "deconv" followed by reducing modulo p, followed by reducing modulo the conway polynomial, and then reducing mod p again, and the result is 0.017s.

请先登录，再回答此问题。

回答（1 个）

arushi
arushi 2024-2-13
Hi Ethan,
Your observation about the performance issues with "gfmul" for larger field sizes is correct. MATLAB's "gftuple" operation generates a full representation of the Galois field elements, which can become very large and memory-intensive as the field size increases. This can lead to significant computational overhead, especially when performing arithmetic operations like multiplication or inversion.
For Galois fields of size GF(p^m) where m is large, it's often more efficient to use polynomial arithmetic rather than the tuple representation. The "gf" object in MATLAB's Communications Toolbox provides a more memory-efficient way to represent elements of a Galois field and perform arithmetic operations.
By using "gf" objects, MATLAB can handle the arithmetic in a more optimized way, which should be faster than using “gftuple” and “gfmul” for large fields.
Regarding your workaround using “gfconv”, that's a valid approach too, but be aware that it relies on manual polynomial reduction, which can be error-prone if not done carefully. The "gf" object handles all these operations internally and ensures correctness.
Hope this helps.
  1 个评论
Ethan Duckworth
Ethan Duckworth 2024-2-13
Thanks for the reply. Unless I'm missing something, the gf tool only generates Galois fields with p=2, and I need p=29.
Also, I know the array is much larger but there's something really dramatic about the slow down, and it really doesn't make sense. Matlab can generate the whole field array, in 1.3 seconds, and it's a 707281 x 4 array, which isn't so large. Finally, once that array is generated, multiplication should be rather trivial: the exponential encoding means that multiplying two elements is the same as adding their row numbers.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Error Detection and Correction 的更多信息

标签

产品


版本

R2021b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by