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 Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 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
Full-text PDF (400 kB) Citations (1)
References:
PDF
HTML
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а
Received: 10.10.2012
English version:
Moscow University Mathematics Bulletin, 2014, Volume 69, Issue 6, Pages 251–257
DOI: https://doi.org/10.3103/S0027132214060047
Bibliographic databases:
Document Type: Article
UDC: 519.95
Language: Russian
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://mathscinet.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:
  • https://www.mathnet.ru/eng/vmumm360
  • https://www.mathnet.ru/eng/vmumm/y2014/i6/p24
    • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024