Generalization to Any Field of Toeplitz Matrix Vector Product Based on Multi-Way Splitting Method and Its Application

Sun-Mi PARK  Ku-Young CHANG  Dowon HONG  Changho SEO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E98-A   No.1   pp.378-383
Publication Date: 2015/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E98.A.378
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Toeplitz matrix vector product,  subquadratic space complexity multiplier,  finite field,  trinomial,  

Full Text: PDF>>
Buy this Article

In several important applications, we often encounter with the computation of a Toeplitz matrix vector product (TMVP). In this work, we propose a k-way splitting method for a TMVP over any field F, which is a generalization of that over GF(2) presented by Hasan and Negre. Furthermore, as an application of the TMVP method over F, we present the first subquadratic space complexity multiplier over any finite field GF(pn) defined by an irreducible trinomial.