JEWeell Home | About Project

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 В НАЯВНОСТІ.
  1. Додатково, заперечення, комплексно-поєднане транспонування, множення на скаляр, множення матриць, зведення в ступінь, Кронекера продукту, оцінки матричних многочленів на квадратної матриці.
  2. Стандартний елементарних рядків і стовпців операції можуть бути виконані на всіх типах матриць.
  3. Записи зберігаються матриці можуть бути змінені, або індивідуально, або по рядку або стовпці. Одного рядка або стовпця можуть бути видалені.
  4. Одному рядку або стовпці вектора може бути обрана з збереженої матриці. В цілому, подматріца зберігається матриця може бути сформована шляхом вибору підродини рядків або стовпців відповідно.
  5. Дві матриці можна з'єднати рядки або стовпці. Розподіляли матриці [A | I] може бути сформована з A. Матриця може бути розгорнута в вектор-стовпець (процес, корисно для знаходження мінімального многочлена матриці).
  6. Формування матриці A-Ti, для використання в розрахунках власного вектора.
  7. Створення спеціальних матриць, таких як одинична матриця, елементарні Йорданії матриць і матриць супутника, а також група матрицях.
  8. Створення матриці скаляри якого (Ij)-го елемента дається просте арифметичне такі вирази, як I + J - I ^ 2 + 3 * J для чисельник і знаменник, може бути створений повністю у межах CMAT.
  9. Знаходження зворотного, сполучений, визначник, характеристичний многочлен і мінімальний багаточлен матриці скалярів, P-1AP. Холецкого розкладання позитивно певна матриця знаходиться: A = L * DL, де L є верхній блок трикутні і D-діагональна матриця. Вихід має діагональні елементи D по діагоналі і вище її діагональні елементи є ті, Л.
  10. Зворотний матриця M цілих чисел тій т можна знайти, при т> 1 є позитивним числом, яке взаємно просто з визначником M.
  11. Пошук наведених рядків ступінчастою формі, рішення лінійних рівнянь, пошуку підстав для нуль-простору N (A) і стовпця-просторі С (А) матриці A. Ці процедури дуже корисні в алгоритми для знаходження Жорданових канонічній формі, або, більш загально, раціональне канонічному вигляді квадратної матриці. (Див. [стаття]).
  12. Обчислення скалярного добутку, довжину і за допомогою Шмідта процес, щоб знайти ортогональний базис для стовпця-простір матриці. Пошук перехресне добуток векторів-рядків (п - 1) х матриці. Знаходження визначника і зв'язаний з полиномиальной матрицею запису.
  13. Пошук Сміт канонічному вигляді матриці B з поліноміальною запису. (Наприклад, при нанесенні на матрицю B = Xi - А, де А-матриця з раціональними чи комплекс раціональних записів, це дає схожість інваріантів, зокрема, ми отримуємо мінімальний багаточлен в якості інваріанта найвищого ступеня).
  14. Ми також отримуємо многочлен матриці P та Q, чиї детермінанти є постійними поліномів, з тим властивістю, що PBQ в Smith канонічній формі.
  15. Елементарні рядків / стовпців матриці операцій з поліноміальною запису.
  16. Друк матриці раціональних чисел у файл або на екран, з точністю до заданого числа десяткових знаків.
  17. Надсилання даних на лінії-принтер.
  18. Файл г (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 На головну
JEWeell

Technical support by @ReuN

Contact Form | Privacy policy | Cookie policy