CMAT

CMAT это программа матрицы калькулятор, написанный на языке C.
Расчеты могут быть выполнены на матрицах с комплексом рациональными коэффициентами с помощью точных процедур арифметике, а также на матрице с элементами модуля г. Есть Unix, DOS и Windows XP версии.
Чтобы запустить под Windows2000 + из окна DOS, пользователь должен сначала загрузить эмулятор DOS от http://dosbox.sourceforge.net/.

Unix, DOS и Windows XP версии, вместе с источником C, могут быть загружены.
Люди, которые используют версии UNIX нужно создать. Cmatrc файл в рабочий каталог, состоящий из двух линий

datpath =.
cmat =.

Есть три калькулятора программ в рамках CMAT: CMATR, CMATCR и CMATM.
CMATR работает над полем рациональных чисел, CMATCR работает поле комплексных рациональных и CMATM работ над полем с р элементов, где р-любое простое число, меньшее 216 = 65536.

Программы используют несколько точных арифметических процедур основано на тех, кто [документацию).

К M0 (= 30) объектов каждого типа могут быть созданы и сохранены для использования в будущих сессиях.

(Rational) numbers: R [0], …, R [M0-1], (rational) matrices: RM [0], …, RM [M0-1]; polynomials (rational): PR [0], …, PR [M0-1]; polynomial (rational) matrices: PRM [0], …, PRM [M0-1];

(Complex rational) numbers CR [0], …, CR [M0-1], (complex rational) matrices CRM [0], …, CRM [M0-1]; polynomials (complex rational): PCR [0] … , PCR [M0-1]; polynomial (complex rational) matrices: PCRM [0], …, PCRM [M0-1];

(Mod p) matrices: mM [0], …, mM [M0-1]; polynomials (mod p): Pm [0], …, Pm [M0-1]; polynomial (mod p) matrices: PmM [0 ], …, PmM [M0-1].

Программа может обрабатывать целые числа произвольного размера. Размер матрицы ограничена только время, затраченное на создание матрицы в вопросе и вычислить с ним. Выполнение раз гораздо менее при расчете с р мода матриц.

РАЦИОНАЛЬНЫЙ / КОМПЛЕКС / MOD P ЧИСЛЕННОЕ ROUTINES В НАЛИЧИИ.

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

Полиномиальные ROUTINES В НАЛИЧИИ.

Сложение, вычитание, умножение, скалярное умножение, возведение в степень, производная, оценки, частное, остаток, наибольший общий делитель, выражая НОД в виде линейной комбинации многочленов участие, свободных от квадратов разложения. Полученные двух многочленов над ℤ [х] и дискриминант многочлена над ℤ [х] может быть найдено. Существует модульного возведения в степень по модулю р многочленов.
Матрица Берлекэмпа из квадратов по модулю р многочлена. (Наш Берлекэмпа матрица является транспонированной матрицей обычного Берлекэмпа.) Факторизация многочленов с рациональными, сложные рациональные или модулю р коэффициентами на неприводимые. Поиск неприводимого данного модуля р степени. Поиск го кругового многочлена. (Той г)

MATRIX ROUTINES В НАЛИЧИИ.

Дополнительно, отрицание, комплексно-сопряженное транспонирование, умножение на скаляр, умножение матриц, возведение в степень, Кронекера продукта, оценки матричных многочленов на квадратной матрицы.
Стандартный элементарных строк и столбцов операции могут быть выполнены на всех типах матриц.
Записи хранятся матрицы могут быть изменены, либо индивидуально, либо по строке или столбце. Однажды строки или столбца могут быть удалены.
Одному строке или столбце вектора может быть выбрана из сохраненной матрицы. В целом, подматрица сохраняется матрица может быть сформирована путем выбора подсемейства строк или столбцов соответственно.
Две матрицы можно соединить строки или столбцы. Распределяли матрицы [A | I] может быть сформирована из A. Матрица может быть развернута в вектор-столбец (процесс, полезно для нахождения минимального многочлена матрицы).

Формирование матрицы A-Ti, для использования в расчетах собственного вектора.
Создание специальных матриц, как единичная матрица, элементарные Иордании матриц и матриц спутника, а также группа матрицах.
Создание матрицы скаляры которого (Ij)-го элемента дается простое арифметическое такие выражения, как I + J – I ^ 2 + 3 * J для числитель и знаменатель, может быть создан полностью в пределах CMAT.
Нахождение обратного, соединен, определитель, характеристический многочлен и минимальный многочлен матрицы скаляров, P-1AP. Холецкого разложения положительно определенная матрица находится: A = L * DL, где L является верхний блок треугольные и D-диагональная матрица. Выход должен диагональные элементы D по диагонали и выше ее диагональные элементы являются те, Л.

Обратная матрица M целых чисел той т можно найти, при т> 1 является положительным числом, которое взаимно просто с определителем M.
Поиск приведенных строк ступенчатой форме, решение линейных уравнений, поиска оснований для нуль-пространства N (A) и столбца-пространстве С (А) матрицы A. Эти процедуры очень полезны в алгоритмы для нахождения Жордановых канонической форме, или, более общо, рациональное каноническом виде квадратной матрицы. (См. [статья]).
Вычисление скалярного произведения, длину и с помощью Шмидта процесс, чтобы найти ортогональный базис для столбца-пространство матрицы. Поиск перекрестное произведение векторов-строк (п – 1) х матрицы. Нахождение определителя и связан с полиномиальной матрицей записи.
Поиск Смит каноническом виде матрицы B с полиномиальной записи. (Например, при нанесении на матрицу B = Xi – А где А-матрица с рациональными или комплекс рациональных записей, это дает сходство инвариантов, в частности, мы получаем минимальный многочлен в качестве инварианта наивысшей степени).

Мы также получаем многочлен матрицы P и Q, чьи детерминанты являются постоянными полиномов, с тем свойством, что PBQ в Smith канонической форме.
Элементарные строк / столбцов матрицы операций с полиномиальной записи.
Печать матрицы рациональных чисел в файл или на экран, с точностью до заданного числа десятичных знаков.
Передача данных в линии-принтер.
Файл г (M0 и ле-J) подготовленной матрицы того же типа (рациональные, с плавающей точкой, комплексной рациональной или модульные) могут быть введены в J массив позиций … J + Р-1.

RUNNING CMAT.

После введения CMAT, пользователь теперь может спускаться через различные уровни, выбирая из двух вариантов экрана. Чтобы подняться через различные уровни, Тип Q, когда это вариант. При выходе из программы, пользователю предоставляется возможность сохранения данных для повторного использования в последующих сессиях.

Вычисления с CMAT.

Чтобы ввести рациональное число и хранить числа в R [0], например, выбрать соответствующий пункт меню и типа N 0.
ПРИМЕЧАНИЕ: Используйте Control-H, а не клавишу возврата, чтобы забой более символов.

Целые числа вводятся как обычные, а не целое рациональных чисел вводятся с косой черты, как целого / натуральное число, например: 1/2, в то время как комплексные числа с ненулевой мнимой части должны заканчиваться я, например: 1/2I представляет собой ( 1/2) я. Ни скобки будут использоваться при вводе номера. Рациональные числа выводятся в «младших членов» с положительным знаменателем.

Некоторые широты допускается относительно расстояния. Например, выражение первого, 1 – я 1 – я представляю тот же комплекс рациональных, в то время как первый представляет собой два числа 1 и-я.

Матрицы вводятся по строкам, конец строки обозначается символом возврата каретки. Пространства отдельные записи в строке. Войдя матрицы RM [0] и RM [1], изделие RM [0] * RM [1] отправляется в РМ [2] (например) или RM [0] RM [1]), выбрав опцию умножения т из меню ниже и введя т 0 1 2.

Rational Matrix Arithmetic
————————————
a j k l: RM [j] + RM [k] -> RM [l]
t j k l: RM [j] * RM [k] -> RM [l]
s j k l: RM [j] – RM [k] -> RM [l]
m j k:-RM [j] -> RM [k]
fjkl: R [j] (RM [k]) -> RM [l] (scalar multiple)
* J k: (RM [j]) * -> RM [k] (transpose)
enjk: RM [j] ^ n -> RM [k] (exponentiation)
z j k l: RM [j] – R [k] I -> RM [l]
p: print numbers and matrices
x: to enter data
q: to exit
————————————

Чтобы прекратить введение полинома или матрицы с клавиатуры, типа Q или любой не алфавитно-цифровой символ при вводе коэффициента. Многочлена по умолчанию или матрицы сохраняются.

Чтобы вычислить 10-й степени СМ [0], выберите опцию электронной сведения в верхнем меню, набрав электронной 10 0 3, чтобы направить вывод в РМ [3]. Ситуация несколько проще с модульной арифметические расчеты. Здесь нет числа хранятся и неотрицательные числа меньше соответствующего модуля вводятся непосредственно, а не сохраняются. Например, чтобы умножить матрицу мМ [0] 5 (Mod 7) и сохранить результат в мм [1], выберите соответствующее меню с помощью строки меню

f, jklp: j * (mM [k]) -> mM [l] (mod p) (scalar multiple)

и типа F 5 0 1 7.

Важно помнить, что при использовании модульной секции арифметика CMAT, операции должны осуществляться только на сохранившиеся объекты одного и того же модуля.

Чтобы завершить ввод преждевременно после ввода первой буквы меню типа Q следует RETURN.

Наконец, для ввода файла г (M0 & ле-J) подготовленной матрицы того же типа (рациональные, с плавающей точкой, комплексной рациональной или модульные) в массиве позиций J … J + R-1, первая линия файл должен содержать количество матриц; следующая строка состоит из строки и столбца первой матрицы, а затем соответствующие строки матрицы. Например, следующий файл представляет собой две матрицы рациональных чисел, 3 х 3 матрицу с последующим 2 х 2 матрицы:

/ * Рациональное файл матрицы * /

23 32/3 5 -7/81/2 12 -57 6 42 21 00 1

Комментарии на алгоритмы, используемые в CMAT

  • Приемы П. Henrici указано в [Buc] [200-201] используется для ускорения операций сложения и умножения рациональных чисел.
  • Жордана-Гаусса метод используется, чтобы найти пониженной строк ступенчатой форме и решать системы линейных уравнений над всеми тремя полями.
  • Соединенный, обратная, определитель и характеристический многочлен матрицы рациональных чисел или комплексных рациональных чисел находят Фаддеева-Леверье метод. (См. [Fad] [177-181]).
  • Для матриц над ℤ р, мы используем модификацию алгоритма через Фробениуса (см. [MCW] [168-175]), чтобы найти характеристический многочлен.
  • По ℤ г, Гаусса-Жордана используется алгоритм, чтобы найти обратную и определитель матрицы. Соединенный находится пользуясь тем, что прил (A) = 0, если ранг (A) и Ле п-2, звание (прил. ()) = 1, если ранг (A) = N-1 и прил (A) = ( Det (A)) A-1 в противном случае.
  • Обратная целая матрица той т найден с помощью присоединенной матрицы и умножение мод м в обратном определитель м мод.
  • Минимальный многочлен мА (х) пхп матрица находится по поиску наименьшее положительное число т, что Am представим в виде линейной комбинации матриц В, …, Am-1.
    Это делается путем развертывания матрицы В, …, Ar в столбце вектора на 1 и R & ле ле м и решая уравнение [0] I + • • + [R-1] Ar-1 = Ar как система n2 уравнений с неизвестными р . Система не будет совпадать для 1 ≤ R ≤ м, но будет иметь единственное решение, когда г = т, что дает минимальный многочлен мА (х) = хт-[м 1] XM-1-• • – [0] .
  • Форма Смит канонической находится по алгоритму [Наг] [111-113]. Скорее алгоритмы существуют (см. [LU2]).
  • Факторизация многочленов ℤ Р [х] осуществляется с использованием метода нахождения нетривиальных фактор в связи с P. Camion (см. [Cam]). Это используется в сочетании с Берлекэмпа матрица многочлена. Для получения информации об этой матрицы см.. [Knu] [420-429]. (Наш Берлекэмпа матрица является транспонированной Кнута).
  • Факторизации многочлена ℤ [х] осуществляется с помощью алгоритма, изложенные в [Муз]. Алгоритм использует степенью набор процедуру тестирования, которая иногда раскрывает неприводимые к более сложным тестов работают. Hensel-Цассенхауза квадратичные и линейные поднятия используются для получения факторизации F (X) по модулю высокой степенью простого. Степень набора тестов также эффект уменьшения количества тестов подразделения, необходимые для определения возможных факторов над ℤ [х] после поднятия завершены.
  • Факторизации многочлена ℚ (I) [х] осуществляется с помощью алгоритма, изложенные в [Май].
  • Квадратов алгоритм разложения для многочленов в связи с DYY Yun и описаны в [Knu] [631-632] используется.
  • Неприводимых многочленов данной степени (той р) строятся с использованием вероятностного алгоритма из [LU2] [145-149].
  • Алгоритм, используемый для расчета результирующей двух многочленов с целыми коэффициентами, изложенные в статье Р. Loos в [Buc] [130].
  • Круговых Фин многочлен (х) вычисляется с помощью алгоритма из [LU2] [354-356], который в свою очередь основан на счета в [Lu1] [58-63]. Факторинг Phipn-1 (х) по ℤ р [х] дает {φ (р-1)} / п унитарный примитивных многочленов степени п над ℤ г.
  • Т-й степени с рационального числа вычисляется с использованием алгоритма из [Ma1].

ЛИТЕРАТУРА

  1. [Cam] P. Camion. A Deterministic Algorithm for Factorizing Polynomials of Fq [x].
  2. Annals of Discrete Mathematics 17 (1983) 149-157.
  3. [Fla] H. Flanders. Scientific Pascal.
  4. 1984, Reston Publishing Company, Reston, Virginia. (Second Edition Birkhäuser, 1995).
  5. [Knu] D.E. Knuth. The Art of Computer Programming, Volume 2.
  6. Second Edition 1981, Addison-Wesley Publishing Company, Reading, Massachusetts.
  7. [Lu2] H. Lüneburg. On the Rational Normal Form of Endomorphisms.
  8. 1987, B.I. Wissenschaftsverlag, Mannheim / Wien / Zürich.
  9. College Mathematics Journal 19 (1988) 174-176.
  10. [Mus] D.R. Musser. Multivariate Polynomial Factorization.

Ресурс: СМАТ

Comments are closed.

Post Navigation