13 521
правка
Изменения
Нет описания правки
: <m>f_j(x_i)</m> — значение j-ой функции базиса в i-ой точке сетки.
: <m>r_j</m> — j-ый нормировочный коэффициент.
Оптимизированный для рекуррентных соотношений алгоритм разложения:
* Интерполировать выбранную подпоследовательность длины N > n на подсчитанную сетку алгоритмом «ближайшего соседа».
* В цикле по ''i = 1..n'':
** <m>c_i = 0</m>
* В цикле по ''i = 1..n'':
** Вычислить и сохранить в памяти все значения <m>f_j(x_i), j = 1 \ldots n</m> с помощью рекуррентных соотношений.
** В цикле по ''j = 1..n'':
*** <m>c_j = c_j + y_i \cdot f_j(x_i) \cdot r_j \cdot w_i</m>
=== Оптимизация ===
ippsMulC_64f(wn, -1, tn, n);
ippsSqrt_64f_I(tn, n);
И последний важный момент — принцип «дискриминантности». Напомним, что расстояние между двумя векторами коэффициентов разложения определяется как <m>\frac{|a-b|}{|a|+|b|}</m>, где <m>|x|=\sqrt{\sum {x}_{i}^{2}}</m> Принцип «дискриминантности» же гласит очевидную вещь: если <m>\frac{\sqrt{{\sum }_{i=0}^{k}{({a}_{i}-{b}_{i})}^{2}}}{|a|+|b|}> \varepsilon</m> уже при k < n, суммирование можно не продолжать, т.к. ''меньше'' ε сумма квадратов уже не станет. Эта идея также использовалась при оптимизации алгоритма. Однако здесь возникает определённое препятствие: суммирование с постоянными условными проверками не векторизуется, т.е., при подсчёте нормы с учётом принципа "дискриминантности" IPP использовать мы уже не можем. Но так как IPP даёт весьма неплохой прирост производительности, можно применить следующий нетривиальный ход: сначала суммировать до ''k = d'', где d - делитель n, больший 1, с использованием векторных операций, потом проверять, не превышен ли порог, потом до ''k = 2d'', потом до ''k = 3d'', и т.д.
=== Алгоритм с учётом индексации ===
С учётом выбранного подхода - индексации одной последовательности и разложения другой "на лету" - алгоритм принимает следующий вид:
* Загрузить входные файлы последовательностей.
* Подсчитать и сохранить в памяти коэффициенты разложения всех подпоследовательностей 1-ой последовательности по выбранному ОНБ.
* Подсчитать и сохранить в памяти нормы всех векторов коэффициентов разложения этих подпоследовательностей.
* По всем сохранённым коэффициентам разложения подпоследовательностей 1-ой последовательности:
** По всем подпоследовательностям 2-ой последовательности:
*** Подсчитать коэффициенты разложения подпоследовательности 2-ой последовательности по выбранному ОНБ.
*** Вычислить норму вектора коэффициентов разложения подпоследовательности 2-ой последовательности.
*** Подсчитать L<sub>2</sub>-расстояние между векторами коэффициентов разложения подпоследовательностей.
*** Поделить подсчитанное расстояние на сумму норм векторов коэффициентов.
*** Сохранить подсчитанное значение как (i, j)-ый элемент матрицы гомологии.
* Записать матрицу гомологии в выходной файл.
=== Сравнение векторов с учётом векторных операций и дискриминантности ===
* Вычислить относительный порог <m>l = (\varepsilon \cdot (s_1 + s_2))²</m>.
* Начальное значение ''f = 0''.
* В цикле:
** С помощью функции IPP <code>ippsNormDiffL2_64f</code> (или 32f, в зависимости от требуемой точности) вычислить норму разности очередных участков длины ''d'' сравниваемых векторов.
** Добавить к ''f'' квадрат полученного значения.
** Если ''f > l'', принять, что вектора «не подобны».
* Если цикл завершился без принятия того, что вектора «не подобны», принять, что вектора подобны.
=== Сравнение ОНБ ===