On complexity of adaptive splines › SPbU Researchers Portal

Standard

On complexity of adaptive splines. / Demjanovich, Yuri K.

In: International Journal of Circuits, Systems and Signal Processing, Vol. 14, 2020, p. 607-615.

Research output: Contribution to journal › Article › peer-review

Harvard

Demjanovich, YK 2020, 'On complexity of adaptive splines', International Journal of Circuits, Systems and Signal Processing, vol. 14, pp. 607-615. https://doi.org/10.46300/9106.2020.14.78

APA

Demjanovich, Y. K. (2020). On complexity of adaptive splines. International Journal of Circuits, Systems and Signal Processing, 14, 607-615. https://doi.org/10.46300/9106.2020.14.78

Vancouver

Demjanovich YK. On complexity of adaptive splines. International Journal of Circuits, Systems and Signal Processing. 2020;14:607-615. https://doi.org/10.46300/9106.2020.14.78

Author

Demjanovich, Yuri K. / On complexity of adaptive splines. In: International Journal of Circuits, Systems and Signal Processing. 2020 ; Vol. 14. pp. 607-615.

BibTeX

@article{52efb6b6039c4111b48f6bb68bf70f88,

title = "On complexity of adaptive splines",

abstract = "The paper discusses various methods of adaptive spline approximations for the flow of function values. It is considered an adaptive compression algorithm, which, for a priori given, has the properties 1) the complexity of the algorithm is proportional to the length of the original flow, 2) by the piecewise linear interpolation of the compression result, it is possible to restore the original flow with an accuracy of 3) the compression result is close to optimal and has O(M) of arithmetic operations. The effectiveness of this approach is demonstrated on rapidly changing initial flows of numerical information in the digital experiment . In addition, the paper presents an exact two-sided estimate for the number O(M2) of arithmetic operations for the optimal solution of the problem of compressing an informational numerical flow of length M with the possibility of recovering this flow with a predetermined accuracy. Provided that the original flow is convex, a compression algorithm is developed with an accurate twosided estimate of the number O(Mlog2M) and with the possibility of recovery with a prescribed accuracy.",

keywords = "Adaptive grid, Algorithms of enlargement, Computational complexity, Spline approximation",

author = "Demjanovich, {Yuri K.}",

year = "2020",

doi = "10.46300/9106.2020.14.78",

language = "English",

volume = "14",

pages = "607--615",

journal = "International Journal of Circuits, Systems and Signal Processing",

issn = "1998-4464",

publisher = "North Atlantic University Union NAUN",

}

RIS

TY - JOUR

T1 - On complexity of adaptive splines

AU - Demjanovich, Yuri K.

PY - 2020

Y1 - 2020

N2 - The paper discusses various methods of adaptive spline approximations for the flow of function values. It is considered an adaptive compression algorithm, which, for a priori given, has the properties 1) the complexity of the algorithm is proportional to the length of the original flow, 2) by the piecewise linear interpolation of the compression result, it is possible to restore the original flow with an accuracy of 3) the compression result is close to optimal and has O(M) of arithmetic operations. The effectiveness of this approach is demonstrated on rapidly changing initial flows of numerical information in the digital experiment . In addition, the paper presents an exact two-sided estimate for the number O(M2) of arithmetic operations for the optimal solution of the problem of compressing an informational numerical flow of length M with the possibility of recovering this flow with a predetermined accuracy. Provided that the original flow is convex, a compression algorithm is developed with an accurate twosided estimate of the number O(Mlog2M) and with the possibility of recovery with a prescribed accuracy.

AB - The paper discusses various methods of adaptive spline approximations for the flow of function values. It is considered an adaptive compression algorithm, which, for a priori given, has the properties 1) the complexity of the algorithm is proportional to the length of the original flow, 2) by the piecewise linear interpolation of the compression result, it is possible to restore the original flow with an accuracy of 3) the compression result is close to optimal and has O(M) of arithmetic operations. The effectiveness of this approach is demonstrated on rapidly changing initial flows of numerical information in the digital experiment . In addition, the paper presents an exact two-sided estimate for the number O(M2) of arithmetic operations for the optimal solution of the problem of compressing an informational numerical flow of length M with the possibility of recovering this flow with a predetermined accuracy. Provided that the original flow is convex, a compression algorithm is developed with an accurate twosided estimate of the number O(Mlog2M) and with the possibility of recovery with a prescribed accuracy.

KW - Adaptive grid

KW - Algorithms of enlargement

KW - Computational complexity

KW - Spline approximation

UR - http://www.scopus.com/inward/record.url?scp=85092255738&partnerID=8YFLogxK

U2 - 10.46300/9106.2020.14.78

DO - 10.46300/9106.2020.14.78

M3 - Article

AN - SCOPUS:85092255738

VL - 14

SP - 607

EP - 615

JO - International Journal of Circuits, Systems and Signal Processing

JF - International Journal of Circuits, Systems and Signal Processing

SN - 1998-4464

ER -

ID: 85827482