References

mais

Моделирование и анализ информационных систем

Modeling and Analysis of Information Systems

1818-10152313-5417

Yaroslavl State University

10.18255/1818-1015-2016-5-603-619

mais-394

Research Article

Оригинальные статьи

Articles

О числовых характеристиках симплекса и их оценках

On Numerical Characteristics of а Simplex and their Estimates

Невский

М. В.

Nevskii

M. V.

доктор физ.-мат. наук, доцент

doctor of science

mnevsk55@yandex.ru

Ухалов

А. Ю.

Ukhalov

A. Yu.

кандидат физ.-мат. наук

PhD

alex-uhalov@yandex.ru

Ярославский государственный университет им. П.Г. Демидова, ул. Советская, 14, г. Ярославль, 150003 РоссияРоссияP.G. Demidov Yaroslavl State University, 14 Sovetskaya str., Yaroslavl 150003, RussiaRussian Federation

2016

20102016

235603619

2016

Невский М.В., Ухалов А.Ю.

Nevskii M.V., Ukhalov A.Y.

Данная работа распространяется под лицензией Creative Commons Attribution 4.0.

This work is licensed under a Creative Commons Attribution 4.0 License.

https://www.mais-journal.ru/jour/article/view/394

Пусть $n\in {\mathbb N}$, $Q_n=[0,1]^n$ --- $n$-мерныйединичный куб. Для невырожденного симплекса $S\subset {\mathbb R}^n$ через$\sigma S$ обозначим образ $S$ при гомотетии относительно центра тяжести $S$с~коэффициентом гомотетии $\sigma$. В работе рассматриваются следующие числовые характеристики симплекса. Обозначим через $\xi(S)$ минимальное $\sigma>0$, такое что $Q_n\subset \sigma S$. Через $\alpha(S)$ обозначим минимальное $\sigma>0$, при котором $Q_n$ принадлежит трансляту симплекса $\sigma S$.Пусть $d_i(S)$ --- \linebreak $i$-й осевой диаметр $S$, т.\,е. максимальная длина отрезка, принадлежащего $S$ и параллельного $i$-й координатной оси. Применяются формулы для вычиcления $\xi(S)$, $\alpha(S)$, $d_i(S)$, полученные ранее первым автором. В~статье рассматривается случай $S\subset Q_n$.

Пусть $\xi_n=\min\{ \xi(S): S\subset Q_n\}. $В работах первого автора была сформулирована гипотеза: если $\xi(S)=\xi_n$, то $\alpha(S)=\xi(S)$. Это утверждение было доказано им для $n=2$ и~случая, когда $n+1$ --- число Адамара, т.\,е. существует матрица Адамара порядка $n+1$. Более сильным утверждением является следующая гипотеза: для любого $n$ существует константа $\gamma \geq 1$, не зависящая от $S\subset Q_n$, с которой выполняется неравенство $\xi(S)-\alpha(S)\leq \gamma (\xi(S)-\xi_n).$Минимальное $\gamma$ c этим свойством обозначается через $\varkappa_n$.Если $n+1$ --- число Адамара, то точное значение $\varkappa_n$ равно 1.Существование $\varkappa_n$ для других $n$ было неясным. В работе с помощью компьютерных методов устанавливается, что $$\varkappa_2 = \frac{5+2\sqrt{5}}{3}=3.1573\ldots $$Доказывается новая оценка$$\xi_4\leq \frac{19+5\sqrt{13}}{9}=4.1141\ldots,$$улучшающая прежний результат $\xi_4\leq \frac{13}{3}=4.33\ldots$Высказывается предположение, что $\xi_4$ в точности равно$\frac{19+5\sqrt{13}}{9}$. Использование этого значения в компьютерных вычислениях даёт значение$$\varkappa_4 = \frac{4+\sqrt{13}}{5}=1.5211\ldots$$

Пусть $\theta_n$ --- минимальная величина нормы интерполяционного проектора на пространство линейных функций $n$ переменных как оператора из $C(Q_n)$ в $C(Q_n)$. Известно, что при любом $n$$$\xi_n\leq \frac{n+1}{2}\left(\theta_n-1\right)+1,$$причём для $n=1,2,3,7$ в этом соотношении достигается равенство.Применение компьютера даёт результат $\theta_4=\frac{7}{3}$.Отсюда следует, что минимальное значение $n$, при котором в последнем соотношении выполняется строгое неравенство, равно 4.

Let $n\in {\mathbb N}$, and let $Q_n=[0,1]^n$ be the $n$-dimensionalunit cube. For a nondegenerate simplex $S\subset {\mathbb R}^n$, by$\sigma S$ we denote the homothetic image of $S$with the center of homothety in the center of gravity of S and theratio of homothety $\sigma$. We apply the followingnumerical characteristics of the simplex.Denote by $\xi(S)$ the minimal $\sigma>0$ with the property$Q_n\subset \sigma S$. By $\alpha(S)$ we denote the minimal$\sigma>0$ such that $Q_n$ is contained in a translateof a simplex $\sigma S$.By $d_i(S)$ we mean the $i$th axial diameter of $S$, i.\,e.the maximum length of a segment contained in $S$ and parallelto the $i$th coordinate axis. We apply the computationalformulae for$\xi(S)$, $\alpha(S)$, $d_i(S)$ which have been proved by the firstauthor. In the paper we discuss the case $S\subset Q_n$.Let$\xi_n=\min\{ \xi(S): S\subset Q_n\}. $Earlier the first author formulated the conjecture:{\it if$\xi(S)=\xi_n$, then $\alpha(S)=\xi(S)$.} He proved this statementfor $n=2$ and the case when $n+1$ is an Hadamard number, i.\,e.there exists an Hadamard matrix of order $n+1$. The followingconjecture is a strongerproposition: {\it for each $n$,there exist $\gamma\geq 1$, not depending on $S\subset Q_n$, such that$\xi(S)-\alpha(S)\leq \gamma (\xi(S)-\xi_n).$}By $\varkappa_n$ we denote the minimal$\gamma$ with such a property.If $n+1$ is an Hadamard number, then the precise value of $\varkappa_n$is 1. The existence of $\varkappa_n$ for other $n$was unclear. In this paper with the use of computer methods we obtainan equality$$\varkappa_2 = \frac{5+2\sqrt{5}}{3}=3.1573\ldots $$Also we prove a new estimate$$\xi_4\leq \frac{19+5\sqrt{13}}{9}=4.1141\ldots,$$which improves the earlier result $\xi_4\leq \frac{13}{3}=4.33\ldots$Our conjecture is that $\xi_4$ is precisely$\frac{19+5\sqrt{13}}{9}$. Applying this valuein numerical computations we achive the value$$\varkappa_4 = \frac{4+\sqrt{13}}{5}=1.5211\ldots$$Denote by $\theta_n$ the minimal normof interpolation projection on the space of linear functions of $n$variables as an operator from$C(Q_n)$in $C(Q_n)$. It is known that, for each $n$,$$\xi_n\leq \frac{n+1}{2}\left(\theta_n-1\right)+1,$$and for $n=1,2,3,7$ here we have an equality.Using computer methods we obtain the result $\theta_4=\frac{7}{3}$.Hence, the minimal $n$ such that the above inequality has a strong formis equal to 4.%, a principal architecture of common purpose CPU and its main components are discussed, CPUs evolution is considered and drawbacks that prevent future CPU development are mentioned. Further, solutions proposed so far are addressed and new CPU architecture is introduced. The proposed architecture is based on wireless cache access that enables reliable interaction between cores in multicore CPUs using terahertz band, 0.1-10THz. The presented architecture addresses the scalability problem of existing processors and may potentially allow to scale them to tens of cores. As in-depth analysis of the applicability of suggested architecture requires accurate prediction of traffic in current and next generations of processors we then consider a set of approaches for traffic estimation in modern CPUs discussing their benefits and drawbacks. The authors identify traffic measurements using existing software tools as the most promising approach for traffic estimation, and use Intel Performance Counter Monitor for this purpose. Three types of CPU loads are considered including two artificial tests and background system load. For each load type the amount of data transmitted through the L2-L3 interface is reported for various input parameters including the number of active cores and their dependences on number of cores and operational frequency.

симплекскубкоэффициент гомотетииосевой диаметрлинейная интерполяцияпроекторнормачисленные методы

simplexcubecoefficient of homothetyaxial diameterlinear interpolationprojectionnormnumerical methods

References1

Климов В. С., Ухалов А.Ю., Решение задач математического анализа с использованием систем компьютерной математики, Ярославский государственный университет им. П. Г. Демидова, Ярославль, 2014, 96 с.

Klimov V. S., Ukhalov A. Yu., Reshenie zadach matematicheskogo analiza s ispolzovaniem sistem kompyuternoi matematiki, P. G. Demidov Yaroslavl State University, Yaroslavl, 2014, 96 pp., (in Russian)]

Невский М. В., “Неравенства для норм интерполяционных проекторов”, Модел. и анализ информ. систем, 15:3 (2008), 28–37.

Nevskij M. V., “Inequalities for the norms of interpolating projections”, Modeling and Analysis of Information Systems, 15:3 (2008), 28–37, (in Russian).

Невский М. В., “Об одном соотношении для минимальной нормы интерполяционного проектора”, Модел. и анализ информ. систем, 16:1 (2009), 24–43.

Nevskij M. V., “On a certain relation for the minimal norm of an interpolational projection”, Modeling and Analysis of Information Systems, 16:1 (2009), 24–43, (in Russian).

Невский М. В., “Об одном свойстве n-мерного симплекса”, Матем. заметки, 87:4 (2010), 580–593.

Nevskii M. V., “On a property of n-dimensional simplices”, Math. Notes, 87:4 (2010), 543–555.

Невский М. В., “О геометрических характеристиках n-мерного симплекса”, Модел. и анализ информ. систем, 18:2 (2011), 52–64.

Nevskii M. V., “On geometric charasteristics of an n-dimensional simplex”, Modeling and Analysis of Information Systems, 18:2 (2011), 52–64, (in Russian).

Nevskii M., “Properties of axial diameters of a simplex”, Discrete Comput. Geom., 46:2 (2011), 301–312.

Невский М. В., Геометрические оценки в полиномиальной интерполяции, Ярославский государственный университет им. П. Г. Демидова, Ярославль, 2012, 218 с.

Nevskii M. V., Geometricheskie ocenki v polinomialnoy interpolyacii, P. G. Demidov Yaroslavl State University, Yaroslavl, 2012, 218 pp., (in Russian).

Невский М. В., “Вычисление максимального в симплексе отрезка данного направления”, Фундамент. и прикл. матем., 18:2 (2013), 147–152.

Nevskii M. V., “Computation of the longest segment of a given direction in a simplex”, Journal of Math. Sciences, 203:6 (2014), 851–854.

Hudelson M., Klee V., Larman D., “Largest j-simplices in d-cubes: some relatives of the Hadamard maximum determinant problem”, Linear Algebra Appl., 241–243 (1996), 519–598.

Lassak M., “Parallelotopes of maximum volume in a simplex”, Discrete Comput. Geom., 21 (1999), 449–462.

Scott P. R., “Lattices and convex sets in space”, Quart. J. Math. Oxford (2), 36 (1985), 359–362.

Scott P. R., “Properties of axial diameters”, Bull. Austral. Math. Soc., 39 (1989), 329–333.

The authors declare that there are no conflicts of interest present.