article · IEEE Transactions on Computers · 2012
Multiway Splitting Method for Toeplitz Matrix Vector Product
M. Anwar Hasan, Christophe Négre
Cited by 31Abstract and details only
Abstract
Computing the product of a Toeplitz matrix and a vector arises in various applications including cryptography. In this paper, we consider Toeplitz matrices and vectors with entries in $({\hbox{\rlap{I}\kern 2.0pt{\hbox{F}}}}_2)$. For improved efficiency in such computations, large Toeplitz matrices and vectors are recursively split and special formulas with subquadratic arithmetic complexity are applied. To this end, we first present a formula for the five-way splitting and then provide a generalization for the $(k)$-way splitting, where $(k)$ is an arbitrary integer. These formulas can be used to compute a Toeplitz matrix-vector product (TMVP) of size $(n)$ with an arithmetic complexity of $(O(n^{\log_k(k(k+1)/2)}))$.
Cite this paper
Hasan, M. A., & Négre, C. (2012). Multiway Splitting Method for Toeplitz Matrix Vector Product. IEEE Transactions on Computers, 62(7), 1467–1471. https://doi.org/10.1109/tc.2012.95
Hasan, M. Anwar, and Christophe Négre. “Multiway Splitting Method for Toeplitz Matrix Vector Product.” IEEE Transactions on Computers, vol. 62, no. 7, 2012, pp. 1467–71, https://doi.org/10.1109/tc.2012.95.
Hasan, M. Anwar, and Christophe Négre. 2012. “Multiway Splitting Method for Toeplitz Matrix Vector Product.” IEEE Transactions on Computers 62 (7): 1467–71. https://doi.org/10.1109/tc.2012.95.
Hasan, M.A. and Négre, C. (2012) ‘Multiway Splitting Method for Toeplitz Matrix Vector Product’, IEEE Transactions on Computers, 62(7), pp. 1467–1471. Available at: https://doi.org/10.1109/tc.2012.95.
@article{hasan2012multiway,
title = {{Multiway Splitting Method for Toeplitz Matrix Vector Product}},
author = {Hasan, M. Anwar and Négre, Christophe},
journal = {IEEE Transactions on Computers},
volume = {62},
number = {7},
pages = {1467--1471},
year = {2012},
doi = {10.1109/tc.2012.95}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.