6CAD-CAE-23 Упорядочение (1014142), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Что касается времени исполнения, то это более тонкий вопрос.

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

Нужно сформировать подходящую схему хранения для L, а чтобы это сделать, нужно определить структуру L. Этот этап распределения памяти также различен по стоимости в зависимости от того, какие упорядочение и схема хранения применены.

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

Обычно время исполнения разреженной матричной технологии примерно пропорционально (или должно быть пропорционально) количеству производимой арифметики. Однако, различия в упорядочении и структуре данных могут привести к большим различиям в константе пропорциональности. Таким образом, число арифметических операций может быть не очень надежной основой сравнения различных методов решения; по крайней мере им пользоваться следует осмотрительно. На константу пропорциональности влияет не только примененная структура данных, но и также архитектура машины, транслятор и операционная система.

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

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

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

Итак:

1. Весь процесс решения системы Ax=b состоит из четырех основных этапов. Доля общего машинного времени, приходящаяся на каждый из них, в общем случае существенно меняется в зависимости от упорядочения и схемы хранения.

2. В соответствии с обстоятельствами конкретной задачи время исполнения некоторых из упомянутых этапов может быть практически несущественным при сравнении различных методов.

11.3. Матрицы и графы

Теория графов представляет собой чрезвычайно полезный инструмент для анализа алгоритмов обработки разреженных матриц.

Характеристики

Список файлов лекций