On some algorithms related to matrices with coefficients in a finite field and their computational complexity
DOI:
https://doi.org/10.54654/isj.v1i21.1032Keywords:
non-singular matrices, multiplication of polynomials, computational complexityTóm tắt
Abstract— In the literature survey, there exist several research papers devoted to the generation of non-singular matrices with coefficients in a finite field. One of these papers refers to the generation of such matrices through the multiplication of polynomials modulus a primitive polynomial. However, the complexity bound given for the algorithm is not accurate. Thus, in this paper, we conduct a new analysis on the complexity of the same. We also remove the restriction of using a primitive polynomial to generate the matrix by using an arbitrary monic polynomial over a finite field whose independent term is distinct from zero.
Downloads
References
Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C.: “Introduction to Algorithms”. MIT Press, Massachusetts, 2022.
Alman, J. and Williams, V. V.: “A refined laser method and faster matrix multiplication”. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 522–539, 2021.
Li, Y.-X., Li, D.-X., and Wu, C.-K.: “How to generate a random nonsingular, matrix in McEliece’s public-key cryptosystem”. In Proceedings Singapore ICCS/ISITA92, pp. 268–269, IEEE, 1992.
Randall, D.: “Efficient generation of random nonsingular matrices”. Random Structures & Algorithms, Vol. 4(1), pp. 111–118, 1993.
Freyre, P., Díaz, N. and Morgado, E.: “Fast algorithm for the multiplication of a row vector by a randomly selected matrix A”. Journal of Discrete Mathematical Sciences and Cryptography, Vol. 12(5), pp. 533–549, 2009.
Murray, S.H.: “The Schereier-Sims algorithm”. Essay submitted to the Department of Mathematics of the Australian National University, 2003.
Holt, D.F., Eick, B. and O’Brien, E.A.: “Handbook of computational group theory”. CRC Press, 2005.
Cannon, J. “A computational toolkit for finite permutation groups”. In Proceedings of the Rutgers Group Theory Year, Vol. 1984, pp. 1–18, 1983.
Green, J. A.: “Sets and groups: A first course in algebra”. Springer, 1988.
Peterson, W.W. and Weldon, E.J.: “Error-correcting codes”. MIT Press, Massachusetts, 1972.
Harvey, D. and Der Hoeven, J.: “Faster polynomial multiplication over finite fields using cyclotomic coefficient rings”. Journal of Complexity, Vol. 54, pp. 101404, 2019.
Cantor, D.G. and Kaltofen, E.: “On fast multiplication of polynomials over arbitrary algebras”. Acta Informatica, Vol. 28(7), pp. 693–701, 1991.
Brent, R.P. and Zimmermann, P.: “Modern Computer Arithmetic”. Cambridge University Press, 2010.
Althoen, S.C., Mclaughlin, R.: “Gauss-jordan reduction: A brief history”. The American Mathematical Monthly, Vol. 94(2), pp. 130–142, 1987.
Press, W.H., Teukolsky, S.A., Vetterling W.T. and Flannery, B.P.: “Numerical recipes: the art of scientific computing”. Cambridge University Press, 1992.
Krishnamoorthy, A. and Menon, D.: “Matrix inversion using Cholesky decomposition”. In 2013 Signal Processing: Algorithms, Architectures, Arrangements and Applications, pp. 70–72, IEEE, 2013.
Vajargah, B.F.: “A way to obtain Monte Carlo matrix inversion with minimal error”. Applied Mathematics and Computation, Vol. 191(1), pp. 225–233, 2007.
Huang, Y. and McColl, W.: “Analytical inversion of general tridiagonal matrices”. Journal of Physics A: Mathematical and General, Vol. 30(22), 1997.
Ries, F., De Marco, T. and Guerrieri, R.: “Triangular matrix inversión on heterogeneous multicore systems”. IEEE Transactions on parallel and distributed systems, Vol. 23(1), pp. 177 – 184, 2011.
Strassen, V. et. al.: “Gaussian elimination is not optimal”. Numerische Mathematik, Vol. 13(4), pp. 354 – 356, 1969.
Coppersmith, D. and Winograd, S.: “On the asymptotic complexity of matrix multiplication”. SIAM Journal on Computing, Vol. 11(3), pp. 472 – 492, 1982.
Traub, J.F.: “Associated polynomials and uniform methods for the solution of linear problems”. SIAM Review, Vol 8(3), pp. 277 – 301, 1966.
Downloads
Published
How to Cite
Issue
Section
License
Proposed Policy for Journals That Offer Open Access
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Proposed Policy for Journals That Offer Delayed Open Access
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication, with the work [SPECIFY PERIOD OF TIME] after publication simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
