CMAT
CMAT це програма матриці калькулятор, написаний на мові C.
Розрахунки можуть бути виконані на матрицях з комплексом раціональними коефіцієнтами за допомогою точних процедур арифметиці, а також на матриці з елементами модулю р. Є Unix, DOS і Windows XP версії.
Щоб запустити під Windows2000 + з вікна DOS, користувач повинен спочатку завантажити емулятор DOS від http://dosbox.sourceforge.net/.
Unix, DOS і Windows XP версії, разом з джерелом C, можуть бути завантажені.
Люди, які використовують версії UNIX потрібно створити. Cmatrc файл в робочий каталог, що складається з двох ліній
datpath=.
cmat=.
(Див. також cmat_bugfix.html для повідомлення про помилку).
Є три калькулятора програм в рамках CMAT: CMATR, CMATCR і CMATM.
CMATR працює над полем раціональних чисел, CMATCR працює поле комплексних раціональних і CMATM робіт над полем з р елементів, де р-будь-яке просте число, менше 216 = 65536.
Програми використовують кілька точних арифметичних процедур засноване на тих, хто [ FLA] [342-357,175-185]. (Див. документацію).
До 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 - я уявляю той же комплекс раціональних, в той час як 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]
f j k l : R[j](RM[k]) -> RM[l] (scalar multiple)
* j k : (RM[j])* -> RM[k] (transpose)
e n j k : 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,j k l p :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].
ЛІТЕРАТУРА
- [Buc] B. Buchberger, G.E. Collins and R. Loos (Editors)
Computer Algebra, Symbolic and Algebraic Computation.
1972, Springer-Verlag Wien, New York.
- [Cam] P. Camion. A Deterministic Algorithm for Factorizing Polynomials of Fq[x].
Annals of Discrete Mathematics 17 (1983) 149-157.
- [Fad] V.N. Faddeeva. Computational Methods in Linear Algebra.
1959, Dover, New York.
- [Fla] H. Flanders. Scientific Pascal.
1984, Reston Publishing Company, Reston, Virginia. (Second Edition Birkhäuser, 1995).
- [Har] B. Hartley and T.O. Hawkes. Rings, Modules and Linear Algebra.
1970, Chapman and Hall, London.
- [Knu] D.E. Knuth. The Art of Computer Programming, Volume 2.
Second Edition 1981, Addison-Wesley Publishing Company, Reading, Massachusetts.
- [Lu1] H. Lüneburg. Galoisfelder, Kreisteilungskörper und Schieberegisterfolgen.
1979, B.I. Wissenschaftsverlag, Mannheim/Wien/Zürich.
- [Lu2] H. Lüneburg. On the Rational Normal Form of Endomorphisms.
1987, B.I. Wissenschaftsverlag, Mannheim/Wien/Zürich.
- [Ma1] K.R. Matthews. Computing mth roots.
College Mathematics Journal 19 (1988) 174-176.
- [Ma2] K.R. Matthews. A Rational Canonical Form Algorithm.
Mathematica Bohemica 117 (1992) 315-324 (pdf file)
- [McW] W.A. McWorter, Jr. An Algorithm for the Characteristic Polynomial.
Mathematics Magazine 56 (1983) 168-175.
- [Mus] D.R. Musser. Multivariate Polynomial Factorization.
J.A.C.M. 22 (1975) 291-308.
- [Tra] B.M. Trager. Algebraic Factoring and Rational Function Integration.
Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, 219-226.
ВИЗНАННЯ
Я вдячний за ці роки за допомогу у виправленні помилок і покращення розробки програми люб'язно надали Майкл Форбс (на початку року), Пітер Адамс і Шон Вікері.
Переведено з http://www.numbertheory.org/cmat/krm_cmat.html
На головну
|