Применение параллельных вычислительных систем является важным направлением развития вычислительной техники. Это вызвано тем, что обычные последовательные ЭВМ имеют ограничение максимально возможного быстродействия, а также практически постоянным наличием вычислительных задач, для решения которых возможностей существующих средств вычислительной техники всегда оказывается недостаточно.
Содержание
Глава 1. Аналитическая часть
.1 Описание предметной области
.1.1 Актуальность работы
.1.2 Предметная область
.2 Инструментарий параллельных вычислений
.2.1 OpenMP
.2.2 .Net TPL
.2.3 Использование OpenMP и библиотеки TPL для решения задач
.2.4 Сравнение возможностей OpenMP и TPL
.3 Линейная алгебра и параллельные вычисления
.3.1 Умножение матриц
.3.2 Возведение в степень
.3.3 Решение систем
.3.4 Решение систем с n правыми частями
.3.5 Детерминант матриц
.3.6 Работа со слабо заполненными матрицами
.4 Проблематика параллельных вычислений
Глава 2. Специальная часть
.1 Выбор программных средств
.2 Выбор средств разработки
.3 Математические методы и специальные алгоритмы решения задачи. Оценка сложности алгоритма решения задачи
.3.1 Решение систем линейных уравнений
.3.2 Вычисление детерминанта
.3.3 Возведение матрицы в степень
Заключение
Глава 1. Аналитическая часть
.1 Описание предметной области
.1.1 Актуальность работы
Применение параллельных вычислительных систем является важным направлением развития вычислительной техники. Это вызвано тем, что обычные последовательные ЭВМ имеют ограничение максимально возможного быстродействия, а также практически постоянным наличием вычислительных задач, для решения которых возможностей существующих средств вычислительной техники всегда оказывается недостаточно.
Проблема создания высокопроизводительных вычислительных систем относится к числу наиболее сложных научно-технических задач современности. Ее разрешение возможно только при всемерной концентрации усилий многих талантливых ученых и конструкторов, предполагает использование всех последних достижений науки и техники и требует значительных финансовых инвестиций. Тем не менее, достигнутые в последнее время успехи в этой области впечатляют.
Организация параллельности вычислений, когда в один и тот же момент выполняется одновременно несколько операций обработки данных, осуществляется, в основном, за счет введения избыточности функциональных устройств (многопроцессорности). В этом случае можно достичь ускорения процесса решения вычислительной задачи, если осуществить разделение применяемого алгоритма на информационно независимые части и организовать выполнение каждой части вычислений на разных процессорах. Подобный подход позволяет выполнять необходимые вычисления с меньшими затратами времени, и возможность получения максимально-возможного ускорения ограничивается только числом имеющихся процессоров и количеством «независимых» частей в выполняемых вычислениях.
Однако следует отметить, что до сих пор применение параллелизма не получило столь широкого распространения, как это ожидалось многими исследователями. Одной из возможных причин подобной ситуации являлась до недавнего времени высокая стоимость высокопроизводительных систем (приобрести супер ЭВМ могли себе позволить только крупные компании и организации). Современная тенденция построения параллельных вычислительных комплексов из типовых конструктивных элементов (микропроцессоров, микросхем памяти, коммуникационных устройств), массовый выпуск которых освоен промышленностью, снизила влияние этого фактора, и в настоящий момент практически каждый потребитель может иметь в своем распоряжении многопроцессорные вычислительные системы достаточно высокой производительности. Наиболее кардинально ситуация изменилась в сторону параллельных вычислений с появлением многоядерных процессоров, которые, уже в 2006 году использовались более чем в 70% компьютерных систем.
Другая основная причина сдерживания массового распространения параллелизма состоит в том, что для проведения параллельных вычислений необходимо «параллельное» обобщение традиционной — последовательной — технологии решения задач на ЭВМ. Так, численные методы в случае многопроцессорных систем должны проектироваться как системы параллельных и взаимодействующих между собой процессов, допускающих исполнение на независимых процессорах. Применяемые алгоритмические языки и системное программное обеспечение должны обеспечивать создание параллельных программ, организовывать синхронизацию и взаимоисключение асинхронных процессов и т.п.
Так же можно выделить следующий ряд общих проблем, возникающих при использовании параллельных вычислительных систем:
· Потеря производительности при организации параллелизма — согласно гипотезе Минского, ускорение, достигаемое при использовании параллельной системы, пропорционально двоичному логарифму от числа процессоров (т.е. при 1000 процессорах возможное ускорение оказывается равным 10).
Подобная оценка ускорения справедлива при распараллеливании определенных алгоритмов. Вместе с тем существует большое количество задач, при параллельном решении которых достигается практически 100%-е использование всех имеющихся процессоров параллельной вычислительной системы.
· Существование последовательных вычислений — в соответствии с законом Амдаля ускорение процесса вычислений при использовании p процессоров ограничивается величиной
где f есть доля последовательных вычислений в применяемом алгоритме обработки данных. К примеру, при наличии всего 10% последовательных команд в выполняемых вычислениях эффект использования параллелизма не может превышать 10-кратного ускорения обработки данных.
Данное замечание характеризует одну из самых серьезных проблем в области параллельного программирования (алгоритмов без определенной доли последовательных команд практически не существует). Однако часто доля последовательных действий характеризует не возможность параллельного решения задач, а последовательные свойства применяемых алгоритмов. Как результат, доля последовательных вычислений может быть существенно снижена при выборе более подходящих для распараллеливания алгоритмов.
· Зависимость эффективности параллелизма от учета характерных свойств параллельных систем — в отличие от единственности классической схемы фон Неймана последовательных ЭВМ, параллельные системы характеризуются существенным разнообразием архитектурных принципов построения. Максимальный эффект от параллелизма может быть получен только при полном использовании всех особенностей аппаратуры; как результат, перенос параллельных алгоритмов и программ между разными типами систем становится затруднительным (если вообще возможен).
Однородность последовательных ЭВМ также является кажущейся, и эффективное использование однопроцессорных компьютеров тоже требует учета свойств аппаратуры. С другой стороны, при всем разнообразии архитектур параллельных систем, тем не менее, существуют и определенные «устоявшиеся» способы обеспечения параллелизма (конвейерные вычисления, многопроцессорные системы и т.п.). Кроме того, инвариантность создаваемых параллельных программ может быть обеспечена и при использовании типовых программных средств поддержки параллельных вычислений (программных библиотек MPI, PVM и др.).
Если существующие программы обеспечивают решение поставленных задач, то, конечно, переработка этих программ не является необходимой. Однако если последовательные программы не позволяют получать решения задач за приемлемое время или же возникает необходимость решения новых задач, то необходимостью становится разработка нового программного обеспечения и эти программы могут реализовываться для параллельного выполнения.
Проблема параллельных вычислений является чрезвычайно широкой областью теоретических исследований и практически выполняемых работ и обычно подразделяется на следующие направления деятельности:
• разработка параллельных вычислительных систем — обзор принципов построения параллельных систем;
• анализ эффективности параллельных вычислений для оценки получаемого ускорения вычислений и степени использования всех возможностей компьютерного оборудования при параллельных способах решения задач. (анализ эффективности организации процессов передачи данных как одной из важных составляющих параллельных вычислений выполняется отдельно);
• формирование общих принципов разработки параллельных алгоритмов для решения сложных вычислительно трудоемких задач;
• создание и развитие системного программного обеспечения для параллельных вычислительных систем, программные реализации которого позволяют разрабатывать параллельные программы и, кроме того, снизить в значительной степени остроту важной проблемы параллельного программирования — обеспечение мобильности (переносимости между разными вычислительными системами) создаваемого прикладного программного обеспечения;
• создание и развитие параллельных алгоритмов для решения прикладных задач в разных областях практических приложений.
Подводя итог всем перечисленным проблемам и замечаниям, можно заключить, что параллельные вычисления являются перспективной и очень привлекательной областью применения вычислительной техники и представляют собой сложную научно-техническую область деятельности. Тем самым, знание современных тенденций развития ЭВМ и аппаратных средств для достижения параллелизма, умение разрабатывать модели, методы и программы параллельного решения задач обработки данных следует отнести к числу важных квалификационных характеристик современного специалиста по прикладной математике, информатике и вычислительной технике.
.1.2 Предметная область
В данной дипломной работе мы проводим разработку приложения, позволяющего провести сравнительный анализ инструментов параллелизма на примерах задач линейной алгебры. Главными объектами анализа являются последовательные и параллельные алгоритмы с применением соответствующих инструментов.
Для каждой задачи мы будем рассматривать идентичные алгоритмы, что бы сравнение было максимально точным.
.2 Инструментарий параллельных вычислений
Количество ядер у процессоров растет год от года. Но многие программы до сих пор умеют использовать только одно. Поэтому для разработки дипломной работы мы выбрали такие среды разработки как Task Parallel Library (.Net TPL) и инструментов Visual Studio, реализующих стандарт OpenMP.
.2.1 OpenMP
Одним из наиболее популярных средств программирования для компьютеров с общей памятью, в настоящее время является технология OpenMP. За основу берётся последовательная программа, а для создания её параллельной версии пользователю предоставляется набор директив, функций и переменных окружения. Предполагается, что создаваемая параллельная программа будет переносимой между различными компьютерами с разделяемой памятью, поддерживающими OpenMP API.
Технология OpenMP нацелена на то, чтобы пользователь имел один вариант программы для параллельного и последовательного выполнения. Однако возможно создавать программы, которые работают корректно только в параллельном режиме или дают в последовательном режиме другой результат. Более того, из-за накопления ошибок округления результат вычислений с использованием различного количества нитей может в некоторых случаях различаться.
Разработкой стандарта занимается некоммерческая организация OpenMP ARB (Architecture Review Board) , в которую вошли представители крупнейших компаний — разработчиков SMP-архитектур и программного обеспечения. OpenMP поддерживает работу с языками Фортран и Си/Cи++. Первая спецификация для языка Фортран появилась в октябре 1997 года, а спецификация для языка Си/Cи++ — в октябре 1998 года. На данный момент последняя официальная спецификация стандарта — OpenMP 3.0.
Интерфейс OpenMP задуман как стандарт для программирования на масштабируемых SMP-системах (SSMP, ccNUMA и других) в модели общей памяти (shared memory model). В стандарт OpenMP входят спецификации набора директив компилятора, вспомогательных функций и переменных среды. OpenMP реализует параллельные вычисления с помощью многопоточности, в которой «главный» (master) поток создает набор «подчиненных» (slave) потоков, и задача распределяется между ними. Предполагается, что потоки выполняются параллельно на машине с несколькими процессорами, причём количество процессоров не обязательно должно быть больше или равно количеству потоков. Примерами систем с общей памятью, масштабируемых до большого числа процессоров, могут служить суперкомпьютеры Cray Origin2000 (до 128 процессоров), HP 9000 V-class (до 32 процессоров в одном узле, а в конфигурации из 4 узлов — до 128 процессоров), Sun Starfire (до 64 процессоров).
Основные преимущества OpenMP:
o За счет идеи «инкрементального распараллеливания» OpenMP идеально подходит для разработчиков, желающих быстро распараллелить свои вычислительные программы с большими параллельными циклами. Разработчик не создает новую параллельную программу, а просто последовательно добавляет в текст последовательной программы OpenMP-директивы.
o При этом, OpenMP — достаточно гибкий механизм, предоставляющий разработчику большие возможности контроля над поведением параллельного приложения.
o Предполагается, что OpenMP-программа на однопроцессорной платформе может быть использована в качестве последовательной программы, т.е. нет необходимости поддерживать последовательную и параллельную версии. Директивы OpenMP просто игнорируются последовательным компилятором, а для вызова процедур OpenMP могут быть подставлены заглушки (stubs), текст которых приведен в спецификациях.
o Одним из достоинств OpenMP его разработчики считают поддержку так называемых «orphan» (оторванных) директив, то есть директивы синхронизации и распределения работы могут не входить непосредственно в лексический контекст параллельной области.
.2.2 Net TPL
Другим популярным средством параллельного программирования является библиотека параллельных задач Task Parallel Library (.Net TPL). Библиотека параллельных задач TPL — предоставляет такие императивные методы, как Parallel.For, Parallel.Foreach и Parallel.Invoke для выполнения параллельных вычислений. Вся работа по созданию и завершению потоков, в зависимости от имеющихся процессоров выполняется библиотекой автоматически. Так же библиотека представляет собой набор открытых типов и API-интерфейсов в пространствах имен System.Threading и System.Threading.Tasks в .NET Framework 4.
Основная цель TPL — повышение производительности труда разработчиков за счет упрощения процедуры добавления параллелизма в приложения. TPL динамически масштабирует степень параллелизма для наиболее эффективного использования всех доступных процессоров. Кроме того, в библиотеке параллельных задач осуществляется секционирование работы, планирование потоков в пуле ThreadPool, поддержка отмены, управление состоянием и выполняются другие низкоуровневые задачи. Используя библиотеку параллельных задач, можно повысить производительность кода, сосредоточившись на работе, для которой предназначена программа.
Начиная с .NET Framework 4 библиотека параллельных задач является предпочтительным способом создания многопоточного и параллельного кода. Однако не всякий код подходит для параллелизации; например, если цикл за каждую итерацию выполняет небольшой объем работ или выполняется для небольшого числа итераций, из-за дополнительной нагрузки, которую параллелизация оказывает на систему, код может выполняться медленнее. Кроме того, параллелизация, как и любой многопоточный код, усложняет выполнение программы. Хотя библиотека параллельных задач упрощает многопоточные сценарии, рекомендуется иметь базовое понимание понятий потоков, например блокировки, взаимоблокировки и состояния гонки, чтобы эффективно использовать библиотеку параллельных задач.
· Одно из самых важных преимуществ этой библиотеки в том, что для создания многопоточного кода требуется минимум изменений;
· Разработчик все еще должен сам явно разбить решение на независимые задачи, которые могут выполняться параллельно, без ущерба для логики, но оптимальным распределением этих задач по потокам уже занимается TPL;
· Эта библиотека усовершенствует многопоточное программирование двумя основными способами. Во-первых, она упрощает создание и применение многих потоков. И во-вторых, она позволяет автоматически использовать несколько процессоров. TPL открывает возможности для автоматического масштабирования приложений с целью эффективного использования ряда доступных процессоров. Благодаря этим двум особенностям библиотеки TPL она рекомендуется в большинстве случаев к применению для организации многопоточной обработки.
1.2.3 Использование OpenMP и библиотеки TPL для решения задач
Основной причиной появления стандартов OpenMP и TPL, служит возросшее значение параллелизма в современном программировании. В настоящее время многоядерные процессоры уже стали обычным явлением. Кроме того, постоянно растет потребность в повышении производительности программ. Все это, в свою очередь, вызвало растущую потребность в механизме, который позволял бы с выгодой использовать несколько процессов для повышения производительности программного обеспечения.
Библиотека TPL определена в пространстве имен System.Threading.Tasks. Но для работы с ней обычно требуется также включать в программу класс System.Threading, поскольку он поддерживает синхронизацию и другие средства многопоточной обработки, в том числе и те, что входят в класс Interlocked.
Применяя TPL, параллелизм в программу можно ввести двумя основными способами. Первый из них называется параллелизмом данных. При таком подходе одна операция над совокупностью данных разбивается на два параллельно выполняемых потока или больше, в каждом из которых обрабатывается часть данных. Так, если изменяется каждый элемент массива, то, применяя параллелизм данных, можно организовать параллельную обработку разных областей массива в двух или больше потоках. Нетрудно догадаться, что такие параллельно выполняющиеся действия могут привести к значительному ускорению обработки данных по сравнению с последовательным подходом.
Несмотря на то что параллелизм данных был всегда возможен и с помощью класса Thread, построение масштабируемых решений средствами этого класса требовало немало усилий и времени. Это положение изменилось с появлением библиотеки TPL, с помощью которой масштабируемый параллелизм данных без особого труда вводится в программу.
Второй способ ввода параллелизма называется параллелизмом задач. При таком подходе две операции или больше выполняются параллельно. Следовательно, параллелизм задач представляет собой разновидность параллелизма, который достигался в прошлом средствами класса Thread. А к преимуществам, которые сулит применение TPL, относится простота применения и возможность автоматически масштабировать исполнение кода на несколько процессоров.
Библиотека TPL позволяет автоматически распределять нагрузку приложений между доступными процессорами в динамическом режиме, используя пул потоков CLR. Библиотека TPL занимается распределением работы, планированием потоков, управлением состоянием и прочими низкоуровневыми деталями. В результате появляется возможность максимизировать производительность приложений .NET. не имея дела со сложностями прямой работы с потоками.
Существует основной подход, который является основой технологии OpenMP, наиболее широко применяемой в настоящее время для организации параллельных вычислений на многопроцессорных системах с общей памятью. В рамках данной технологии директивы параллелизма используются для выделения в программе параллельных областей (parallel regions), в которых последовательный исполняемый код может быть разделен на несколько раздельных командных потоков (threads). Далее эти потоки могут исполняться на разных процессорах вычислительной системы. В результате такого подхода программа представляется в виде набора последовательных (однопотоковых) и параллельных (многопотоковых) участков программного кода. Подобный принцип организации параллелизма получил наименование «вилочного» (fork-join) или пульсирующего параллелизма.
Идея технологии OpenMP состоит в следующем. За основу берется последовательная программа, а для создания ее параллельной версии предоставляется набор директив. Стандарт OpenMP разработан для языков Фортран, С и С++. Весь текст программы разбивается на последовательные и параллельные области. В начальный момент времени порождается нить-мастер или «основная» нить, которая начинает выполнение программы со стартовой точки. При входе в параллельную область порождаются дополнительные нити. После порождения каждая нить получает свой уникальный номер, причем нить-мастер всегда имеет номер 0. Все нити исполняют один и тот же код, соответствующий параллельной области. При выходе из параллельной области основная нить дожидается завершения остальных нитей, и дальнейшее выполнение программы продолжает только она. В параллельной области все переменные программы разделяются на два класса: общие (SHARED) и локальные (PRIVATE). Общая переменная всегда существует лишь в одном экземпляре для всей программы и доступна всем нитям под одним и тем же именем. Объявление локальной переменной вызывает порождение своего экземпляра данной переменной для каждой нити. Изменение нитью значения своей локальной переменной не влияет на изменение значения этой же локальной переменной в других нитях.
Все директивы OpenMP представлены в программе в виде комментариев и начинаются, согласно синтаксису Фортран, на один из трех символов: !, C или *.
Для определения параллельных областей программы используется пара директив
!$OMP PARALLEL
< параллельный код программы >
!$OMP END PARALLEL
Для выполнения кода, расположенного между данными директивами, дополнительно порождается OMP_NUM_THREADS()-1 нитей. Процесс, выполнивший данную директиву (нить-мастер), всегда получает номер 0. Все нити исполняют код, заключенный между данными директивами. После END PARALLEL автоматически происходит неявная синхронизация всех нитей, и как только все нити доходят до этой точки, нить-мастер продолжает выполнение последующей части программы, а остальные нити уничтожаются.
Все порожденные нити исполняют один и тот же код. Для распределения работы между ними часто используется директива DO. Иными словами если в последовательной программе встретился оператор цикла DO то, используя директивы
!$OMP DO
!$OMP END DO
его можно распараллелить в параллельной части программы.
.2.4 Cравнение возможностей OpenMP и TPL
Для сравнения возможностей следует рассмотреть и сравнить некоторые инструменты параллелизма OpenMP и библиотеки TPL. При постоянном применении одной из технологии и любого инструмента важно знать об особенностях, которые они могут предоставить. Для использования данных инструментов в параллельном программировании следует рассмотреть их с точки зрения следующих задач:
· Обработка исключений;
· Планирование вычислений;
· Управление циклом;
· Установка параметров вычислений.
Первой рассматриваемой задачей является обработка исключений. Очевидно, что при работе приложений часто возникают исключительные ситуации, связанные с какими-либо внешними или внутренними ошибками. Для повышения безопасности и надежности кода и приложения в целом необходимо использовать механизм, который позволяет обработать исключительную ситуацию, а не обрушить работу приложения.
В TPL основные функции представлены классами Task и Parallel. Напомним, что класс Task представляет собой отдельную асинхронную операцию — задачу, а класс Parallel — методы для итеративного и функционального распараллеливания. При параллельном выполнении задач, в любой из них может произойти исключительная ситуация. В TPL при появление такой ситуации возможна корректная обработка.
Исключения в одном потоке не могут напрямую повлиять на работу других потоков. При этом исключения могут появляться в двух и более потоках одновременно. В TPL механизм обработки исключений представлен следующим образом: в момент появления ошибки возникает исключение, которое завершает поток и передается вверх по уровню. Такая же ситуация происходит и в остальных потоках. После завершения всех задач в TPL все исключения собираются в одно — AggregateException. Далее композитное исключение может быть обработано после завершения параллельного блока кода. У класса AggregateException есть метод Handle, который позволяет обработать все включенные в него исключения.
OpenMP не предоставляет средств для внешних обработок исключений. Однако, внутри параллельных регионов есть возможность использовать механизм исключений. При этом на данный механизм налагаются жесткие ограничения. Все исключения не должны покидать параллельный регион, который формируется директивами for и section. То есть, все исключения должны быть обработаны именно в параллельном регионе. При выходе исключения за параллельный регион может произойти сбой приложения. Если же есть необходимость во внешней передачи сообщения об ошибке, то для этого следует применять другие механизмы.
Другим не менее важным механизмом является планирование вычислений. Под планированием в нашем случае можно представить процесс распределения задач и потоков. Так, распараллеливая цикл, его итерации можно объединить в группы и задать выполнение каждой группы итераций определенному потоку.
В рассматриваемых инструментариях присутствует механизм планирования, однако его реализации отличаются.
В TPL планирование и распределение вычислений по потокам осуществляется автоматически. Стоит отметить тот факт, что программист не может явно повлиять на этот процесс.
В OpenMP существует несколько стратегий планирования:
· Static — групповое распределение вычислений. Есть возможность явно указать размер группы. Группы распределяются по нитям от нулевой и до последней, затем процесс повторяется опять же начиная с нулевой нити.
· Dynamic — динамическое распределение вычислений с определенным размером группы.
· Guided — динамическое распределение вычислений, при этом размер группы вычислений постепенно уменьшается до некоторой заданной величины прямо пропорционально количеству нераспределённых вычислений и обратно пропорционально количеству нитей.
· Auto — стратегия распределения устанавливается компилятором или во время выполнения.
· Runtime — стратегия распределения устанавливается во время выполнения приложения.
Далее стоит рассмотреть возможности для управления циклом. При использовании обычных циклов предоставляются два способа для управления итерациями — пропуск итерации и прерывания цикла. Для этих целей определенны такие ключевые слова как continue и break.
Для параллельных циклов пропуск итерации не является существенным, поэтому реализации оператора continue не предусмотрено.
В TPL возможности для управления итерациями цикла реализованы в классе ParallelLoopState. Для объектов этого класса определенны два метода — Break и Stop.
Метод Break позволяет прервать выполнение цикла для всех итераций после текущей. При этом, если в какой-то момент времени в одной из итераций вызван данный метод, то все запущенные итерации продолжат свою работу, а далее будут выполнены только итерации с меньшим номером.
Метод Stop явно указывает на то, что в цикле должны быть завершены выполняемые итерации, а оставшиеся итерации не должны быть запущены.не предоставляет явных механизмов для управления итерациями. При этом использование стандартных операторов завершения цикла запрещается.
Так же стоит рассмотреть оба инструментария с точки зрения возможности установки дополнительных параметров. В OpenMP присутствуют методы для явного задания количества нитей, порождаемых в параллельных регионах. В TPL такая возможность отсутствует.
Ниже в таблице приведено краткое сравнение инструментариев по вышеперечисленным критериям.
.3 Линейная алгебра и параллельные вычисления
Линейная алгебра представляет собой раздел математики, который исследует векторы, линейные и векторные пространства, линейные системы уравнений и линейные отображения. Как дисциплина линейная алгебра является важным разделом математики, поскольку векторные пространства широко встречаются в программировании. Линейная алгебра хорошо подходит для проверки эффективности распараллеливания систем при больших значениях n, а так же довольно легко распараллеливается.
В данной дипломной работе мы рассмотрим основные операции над матрицами и их определителями:
· Умножение матриц;
· Возведение в степень;
· Решение систем;
· Детерминант матриц;
· Работа со слабо заполненными матрицами.
Дальше мы рассмотрим поставленные задачи.
.3.1 Умножение матриц
Произведением матрицы A = (aij) размера m×n и матрицы B = (bij) размера n×l называется матрица C = (cij) = A · B размера m×l, элементы которой определяются формулой:
То, что матрица C является произведением матриц A и B, записывается в виде C = A·B.
Заметим, что произведение матриц A и B определено только, если число столбцов матрицы A равно числу строк матрицы B. Умножение матриц хорошо подходит для её распараллеливания, так как элементы матрицы C можно вычислять независимо друг от друга.
.3.2 Возведение в степень
Для любой квадратной матрицы 
(n-ro порядка) определено произведение 
(матрицы 
на себя). Поэтому можно говорить о целой неотрицательной степени матрицы, определяя последовательно:
Заметим, что степени 
и 
одной и той же матрицы 
перестановочны.
Поэтому справедливы обычные свойства степеней:
с натуральными показателями.
.3.3 Решение систем
Задача о порядке перемножения матриц — классическая задача динамического программирования, в которой дана последовательность матриц <#»786178.files/image012.gif»> и требуется минимизировать количество скалярных операций для вычисления их произведения. Матрицы предполагаются совместимыми по отношению к матричному умножению (то есть количество столбцов 
совпадает с количеством строк 
матрицы).
Произведение матриц — ассоциативная <#»786178.files/image015.gif»> размерами соответственно 20×200, 200×10 и 10×100. Существует 2 способа их перемножения (расстановки скобок):
и 
.
В первом случае нам потребуется 20·200·10 + 20·10·100 = 60000 скалярных умножений, а во втором случае 200·10·100 + 20·200·100 = 600000 умножений — как мы видим разница довольно большая. Из этого сделаем вывод, и поэтому может быть выгоднее потратить некоторое время на предобработку, решив, в каком порядке лучше всего умножать, чем умножать сразу в лоб.
Таким образом, даны n матриц:
