ILLUSTRATIVE ALGORITHMS



© Nickolay Balonin, 25.10.2014

Hadamard-type matrix catalogue and on-line algorithms



MAXIMUM DETERMINANT MATRICES



BM-matrix A5 and histogram of its entries


Initial algorithm for orders 3, to 7, to 9, to 13, to 15, .. observe the difference. For n=4 program returns Hadamard matrix H4, for n=6 program return Belevitch C6, and so on.

Two-circulant procedures:

Эффективность итераций зависит от сортировки столбцов по признаку первенства наиболее изменяемых – это подталкивает вращение ортов. Коэффициент сжатия элементов полезно последовательно ослаблять, итерационно увеличивая порог функции насыщения

pk=apk–1+(1–a),


где pk – порог ограничения амплитуды элементов матрицы относительно максимального коэффициента (текущего значения m-нормы), a<1 – параметр инерции процесса.



Функции насыщения можно менять


Алгоритм Прокруста. Необходимым качеством сжимать m–норму обладает функция насыщения ее элементов f1(), см. рис. 1, дополняемая последующей ортогонализацией столбцов матрицы f2()

Mi = f2(f1(Mi–1)).

Рисунок 1. Вид функции насыщения элементов


У матриц эффективность поисковых итераций зависит от начальных условий и алгоритма перестановок столбцов. Недостаток и, одновременно, достоинство итерационного алгоритма состоит в том, что ее продуктом может являться, в том числе, и локальный оптимум. Для его поиска нелинейность (функцию f1) можно варьировать, меняя, тем самым, искомые аттракторы. В частности, рекомендуется с ростом номера итерации повышать уровень насыщения. Несложно создаются: посередине – сжатие, внизу – область растяжения, см. рис. 2.


Рисунок 2. Вид нелинейной функции насыщения на разных стадиях итерационного процесса


Рассматриваемый итерационный подход к поиску М-матриц, при всей его простоте, продуцирует практически все те матрицы Адамара и Белевича, которые определили становление этого научного направления, и которые исторически были получены совсем другими способами. Излишне аргументировать, пожалуй, ту точку зрения, что в науке ценятся альтернативные способы решения даже известных задач, не говоря о тех, которые обещают расширение существующего знания. Отметим, что в такой постановке задача, пожалуй, ставится впервые.

На множестве комплексных чисел квадратичная задача (итерации квадратичной функции) породила представления о точках бифуркации, хаотических аттракторах, фракталах Мандельброта и Джулиа и др. На множестве ортогональных матриц квадратичная функция выступает как уравнение связи при минимизации модульного, в общем, критерия.

Press Run, we will see, how program finds maximim determinat matrix, order n=2v. We can see max among ξ=Aa+Bb besides of the first element. Histogram builder commented by // to get up speed.

Procedue with weighing matrix decompression.

DRAGOMIR'S SDS-LIBRARY

WILLIAMSON MATRICES


Williamson matrices catalogue up to orders v=59, n=4v, mentions the first (found by Dragomir) problem order v=35. These A, B, C, D matrices have non symmetric placement of B and C, symmetric form with symmetric A and B=C is good Propus resolved by Dragomir for case v=35.



Match: H16 and Good Propus H40



Good Propusi: H36 and H44


ONE SHOULDER PROCEDURE

SET INDEX OF SYMMETRY

A fast algorithm to search Golay sequences

SOME ALGORITHMS BASED ON PERMUTATIONS





Index 5,5 of grain symmetry [a,flip(a),..]: H32 and H40




Index 6,[6] of B-asymmetry [1,b,..,flip(–b)]: H32 and H40


Weighing matrices

COMMON SYMMETRIC PART AND TAIL



Common symmetric part H32 5,5, tail 2



Common symmetric part H40 5,5, tail 4


CONVERSION SEQUENCES TO SDS

Rambler's Top100