Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Vestnik Moskov. Univ. Ser. 1. Mat. Mekh.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2014, Number 6, Pages 24–31 (Mi vmumm360)  

This article is cited in 1 scientific paper (total in 1 paper)

Mathematics

The arithmetic computational complexity of linear transforms

S. B. Gashkov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: Quadratic and superquadratic estimates are obtained for the complexity of computations of some linear transforms by circuits over the base $\{x+y \}\cup \{ax: \vert a \vert \leq C \}$ consisting of addition and scalar multiplications on bounded constants. Upper bounds $O(n\log n)$ of computation complexity are obtained for the linear base $\{ax+by: a,b \in {\mathbb R}\}$. Lower bounds $\Theta(n\log n)$ are obtained for the monotone linear base $\{ax+by: a, b > 0\}$.

Key words: binomial transform, Stirling's transforms, Lah's transform, Pascal's triangle, Pascal's triangle modulo $p,$ Stirling's triangles, Serpinsky's matrix, Hadamar–Silvester matrix, Gauss's coefficients, Galois's coefficients, computational complexity, schemata over bases of arithmetical and linear operations

Funding Agency Grant Number
Russian Foundation for Basic Research 11-01-00508
11-01-00792


Full text: PDF file (400 kB)
References: PDF file   HTML file

English version:
Moscow University Mathematics Bulletin, 2014, 69:6, 251–257

Bibliographic databases:

UDC: 519.95
Received: 10.10.2012

Citation: S. B. Gashkov, “The arithmetic computational complexity of linear transforms”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2014, no. 6, 24–31; Moscow University Mathematics Bulletin, 69:6 (2014), 251–257

Citation in format AMSBIB
\Bibitem{Gas14}
\by S.~B.~Gashkov
\paper The arithmetic computational complexity of linear transforms
\jour Vestnik Moskov. Univ. Ser.~1. Mat. Mekh.
\yr 2014
\issue 6
\pages 24--31
\mathnet{http://mi.mathnet.ru/vmumm360}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3370847}
\transl
\jour Moscow University Mathematics Bulletin
\yr 2014
\vol 69
\issue 6
\pages 251--257
\crossref{https://doi.org/10.3103/S0027132214060047}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84920505645}


Linking options:
  • http://mi.mathnet.ru/eng/vmumm360
  • http://mi.mathnet.ru/eng/vmumm/y2014/i6/p24

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. A. Akhrem, V. Z. Rakhmankulov, K. V. Yuzhanin, “On the complexity of the reduction of multidimensional data models”, Sci. Tech. Inf. Process., 44:6 (2017), 406–411  crossref  isi  scopus
  • Number of views:
    This page:41
    Full text:11
    References:2

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021