2007 | OriginalPaper | Buchkapitel
Deterministic Length Reduction: Fast Convolution in Sparse Data and Applications
verfasst von : Amihood Amir, Oren Kapah, Ely Porat
Erschienen in: Combinatorial Pattern Matching
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper a deterministic algorithm for the length reduction problem is presented. This algorithm enables a new tool for performing fast convolution in sparse data. The proposed algorithm performs the convolution in
$O(n_1 \log^3 n_1)$
, where
n
1
is the number of non-zero values in
V
1
. This algorithm assumes that
V
1
is given in advance, and the
V
2
is given in running time.