LEC-25 (Материалы к лекциям)

13

Лекция № 25

10. Общие проблемы математического обеспечения и

алгоритмизации численных методов

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

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

Выделим 4 аспекта, лежащие в основе разработки математического

обеспечения:

1. Общие цели: создать мощные вычислительные средства для решения задач пользователя.

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

3. Необходимые операции: в каждой области вычислений существуют определенные типовые задачи, которые должны быть реализованы и

представлены в виде языковых операций.

4. В математическом обеспечении должны быть сконцентрированы

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

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

Первый и очевидный подход состоит в разработке нового языка

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

матричной алгебры.

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

допускать применение операторов вида:

A(I,J)=INTEGRAL(F(X,I,J) X=1,2 TO 5)

SOLVE A X = B FOR X

FMIN(I)=MIN(MIN(F(X,J,I) X=1,2 TO 3)J=1 TO 6)

Практика показала, что создание таких языков возможно, хотя они,

естественно потребуют значительно больших вычислительных ресурсов, чем Фортран, Паскаль и т.д.

У современных языков общего назначения по-видимому, нет хорошей перспективы:

а) трудно надеяться, что новый язык будет широко использоваться;

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

места.

Второй подход. Так как перспективы языков общего назначения,

обладающих мощными операциями, туманны, во многих областях появились языки специального назначения (проблемно-ориентированные языки). Эти

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

области.

Язык, на котором хотел бы работать пользователь, должен содержать подходящие существительные (структуры данных) и глаголы (операции), а также много прилагательных. Такой подход развит, например, в

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

проводить обширные и осмысленные вычисления.

Часто эти пользователи также мало знают о методах статистических

вычислений.

Можно ожидать, что каждая область знаний будет иметь свою

собственную систему, и в конце концов основная масса вычислений будет

проводиться скорее всего на основе этих систем, а не посредством

использования языков общего назначения.

Ранним и характерным примером таких систем является система NASTRAN. Она насчитывала 300000 операторов языка Фортран, имела

руководство для пользователя объемом 2000 страниц и введение 1200 стр. Стоимость разработки - более 10 млн. долларов.

Она позволила освободить инженеров от кодирования на Фортране и

предоставила им более мощные средства, разработанные специалистами в

области применения вычислительной техники.

Третий подход состоит в обеспечении доступа к мощным операциям

через библиотеки программ. Если не разработан хороший

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

назначения, представляют собой лучший способ использования знаний

экспертов.

Тем не менее, по-видимому, проблемно-ориентированные языки могут стать веянием будущего.

Что касается алгоритмических языков, то необходимо сделать следующее замечание.

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

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

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

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

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

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

Цели, преследуемые при разработке алгоритмов

1. Скорость. 2. Экономия памяти. 3. Надежность. Точность.

5. Простота.

Поясним понятие надежности.

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

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

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

Качества, которыми должна обладать система.

Мощность, Гибкость, Легкость в использовании, Портабельность, Легкость модификации, Надежность в работе.

Мощность - решать трудные задачи широкого круга.

Гибкость - решать задачи с вариациями.

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

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

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

ОСТАНОВ ЦП В ЯЧЕЙКЕ 094637, который произошел в подпрограмме ТАИНСТВ, о которой пользователь никогда не слышал.

Противоречивость целей в разработке матобеспечения.

Типичные противоречия

1. Гибкость и легкость использования.

2. Портабельность и эффективность.

3. Надежность и эффективность.

4. Особенности человеческого восприятия информации и лаконичность описания программ.

5. Ограничения языков программирования и легкость и использовании программ.

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

Алгоритмизация численных методов

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

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

Многие полезные для практики двумерные задачи теории поля приводят к матричным уравнениям с 10³ - 10⁴ переменными, а для расчета трехмерных векторных полей в сложных геометрических структурах может потребоваться 510⁵ - 2510⁵ переменных. Для современных машин решение совместной системы ста уравнений не составляет проблемы, независимо от структуры матрицы коэффициентов. Систему тысячи уравнений также можно легко решить, если матрица коэффициентов содержит много нулей и программа организована так, чтобы использовать это преимущество. При полной матрице коэффициентов, содержащей всего несколько нулевых элементов, или вовсе не содержащей их, 10³ уравнений - довольно большое число, т.к. для запоминания только матрицы коэффициентов потребуется около 4 мгб памяти ЭВМ.

По мере того как растут производительность и быстродействие вычислительных машин, растут размеры матриц. В 1968 г. типо­вой практической задачей считалось решение линейной алгебраи­ческой системы порядка 5000; систему порядка 10 000 или более оценивали как «большую» [Tinney, 1969; Willoughby, 1971]. В 1978 г. появилось сообщение [Kolata, 1978] о переопреде­ленной задаче с 2.5 млн. уравнений и 400 000 неизвестными; в 1981 г. размеры этой задачи еще больше выросли [Golub, Plemmons, 1981]: 6 000 000 уравнений при прежнем количестве неиз­вестных. Матрица задачи имеет 2.4 х 10¹² элементов, большая часть которых нули; это — разреженная матрица. Та же тенден­ция к увеличению размеров наблюдается в спектральных расчетах, где «большой» называют матрицу порядка 4900 или 12 000 [Cul-lum, Willoughby, 1981; Parlett, 1980]. Будут ли порядки матричных задач расти и дальше? Ответ: ДА. И будет ли поспевать за этим ростом наша способность решать большие задачи? Ответа нет.

Но это только одна сторона вопроса. Другая сторона — компьютерный взрыв. РС имеют сейчас большую произво­дительность, нежели имели два-три десятка лет назад большие ма­шины. Значит ли это, что пользователи РС могут решать матричные задачи только таких порядков, как двадцать-тридцать лет тому назад?

Сейчас владелец РС может не слишком заботиться о стои­мости счета; основные ограничения — память и длительность вычислений. На большой ма­шине с ростом порядка матричной задачи быстро растет и стои­мость ее решения, что связано с увеличением и трудозатрат, и памяти. Общая стоимость становится здесь решающим фактором. Как минимизировать эту стоимость для конкретной задачи и вычислительной установки?

Технология разреженных матриц является сейчас вполне установившейся дисциплиной, определенной как «искусство обращаться с раз­реженными матрицами» [Нагагу, 1971 ]. Она представляет собой замечательный сплав теоретических достижений, численной прак­тики и здравого смысла. Она не только служит важным вычисли­тельным средством во многих прикладных областях, но и сама по себе составляет ценный вклад в об­щий процесс развития машинного программного обеспечения. Для ряда матричных задач, основываясь на идеях, появившихся за последние тридцать лет, удалось создать почти оптимальные алгоритмы. Исследования в этой области в настоящее время очень активны, и спектр приложений постоянно расширяется. Технология разреженных матриц существует и будет сущест­вовать.

Технология разреженных матриц применяется почти во всякой области, где вообще используются матрицы. Тому, кто интере­суется конкретным приложением, будет полезно изучить литературу, где это приложение описано в деталях. Существует библиографический обзор [Duff, 1977], систематизированный в соответствии с приложе­ниями. Много статей, посвященных различным приложениям, можно найти в трудах конференции IMA 1980 г. [Duff, 1981] и других публикациях.