Архив статей журнала
Цель работы - представить преобразование метода Леверье решения полной проблемы собственных значений с видоизменением Д. К. Фаддеева, при котором достигается максимально параллельная форма преобразуемого метода с квадратично-логарифмической временной сложностью для одновременного определения коэффициентов характеристического полинома и всех собственных векторов матрицы. Показано, что данная оценка временной сложности сохраняется, если для поиска корней характеристического полинома применить параллельный метод их вычисления на основе устойчивой адресной сортировки. Предложенное преобразование опирается на элементарное приравнивание коэффициентов при одинаковых степенях матриц в исходном алгоритме вычисления собственных векторов. В результате матрица всех собственных векторов, соответствующая отдельно взятому собственному значению, выражается в виде матричного полинома с числовыми коэффициентами. Рассматриваемые преобразования и их результаты относятся к случаю, когда все собственные числа матрицы различны. Метод распространяется на преобразование подобия, при этом обе матрицы преобразования выражаются в конструктивной форме. Аналогично представлена связь и структура матриц собственных векторов, отвечающих каждому собственному числу исходной матрицы, и диагональной матрицы, полученной в результате преобразования подобия. Все вычислительные операции допускают параллельное выполнение с сохранением квадратично-логарифмической оценки временной сложности для нахождения полной совокупности рассматриваемых алгебраических объектов в границах метода Леверье с видоизменением Д. К. Фаддеева. Дополнительно представлены структурные соотношения между матричными полиномами, представляющими собственные векторы, конструктивно указана связь между матрицей собственных векторов и обратной матрицей. Работа включает явные формулы собственных векторов матрицы, а также их видоизменений в случае преобразования подобия. Формулы применимы для оценки возмущений в приложениях к задачам механики.
Целью работы является представление метода бинарного сложения n+1-разрядных двоичных чисел, в котором не используется вычисление переноса. Для сложения двух двоичных полиномов выполняется предварительный шаг - параллельно по всем разрядам слагаемых складываются пары коэффициентов равного веса. Двоичные коэффициенты разрядных сумм размещаются согласно весу, образуя двухрядный код промежуточной суммы. При этом все переносы оказываются взаимно отделенными парами промежуточных нулевых коэффициентов равного веса. Цепочки единиц, не содержащие переноса, также отделены парами промежуточных нулевых коэффициентов равного веса друг от друга и от цепочек переноса. Цепочки идентифицируются по граничным значениям их двухрядного кода. На этой основе цепочки единиц, не содержащие переноса, параллельно по всем разрядам переписываются из верхнего ряда в нижний ряд двухрядного кода с сохранением веса коэффициентов. С помощью электронно-логической схемы это выполняется за время переключения логического элемента. Оставшиеся в верхнем ряду цепочки переноса тривиально преобразуются в однорядный код с численной реализацией переноса. Преобразование выполняется параллельно по всем разрядам также за время переключения логического элемента. Остается переписать единичные цепочки, не содержащие переноса, из нижнего ряда в верхний, чтобы получить окончательный однорядный двоичный код суммы входных слагаемых. Время сложения - O(1), число элементов сумматора - O(n). Приводятся обоснования результатов, примеры численных преобразований, электронно-логическая схема поразрядно-параллельной обработки. Метод распространяется на произвольные позиционные системы счисления с натуральным основанием. Наиболее актуальные приложения связаны с ускорением обработки потока арифметических операций и с увеличением точности вычислений в процессах численного моделирования.