Rationale for Ada 2005: Predefined library

RUSTOPBACKNEXT

ENG

6. Numerics annex

@ When Ada 95 was being designed, the Numerics Rapporteur Group pontificated at length over what features should be included in Ada 95 itself, what should be placed in secondary standards, and what should be left to the creativeness of the user community.

@ A number of secondary standards had been developed for Ada 83. They were

@ The first two, 11430 and 11729, were incorporated into the Ada 95 core language. The elementary functions, 11430, (Sqrt, Sin, Cos etc) became the package Ada.Numerics.Generic_Elementary_ Functions in A.5.1, and the primitive functions, 11729, became the various attributes such as Floor, Ceiling, Exponent and Fraction in A.5.3. The original standards were withdrawn long ago.

@ The other two standards, although originally developed as Ada 83 standards did not become finally approved until 1998.

@ In the case of 13814, the functionality was all incorporated into the Numerics annex of Ada 95 as the package Ada.Numerics.Generic_Complex_Elementary_Functions in G.1.2. Accordingly the original standard has now lapsed.

@ However, the situation regarding 13813 was not so clear. It covered four areas

  1. a complex types package including various complex arithmetic operations,
  2. a real arrays package covering both vectors and matrices,
  3. a complex arrays package covering both vectors and matrices, and
  4. a complex input–output package.

@ The first of these was incorporated into the Numerics annex of Ada 95 as the package Ada.Numerics.Generic_Complex_Types in G.1.1 and the last similarly became the package Ada.Text_IO.Complex_IO in G.1.3. However, the array packages, both real and complex, were not incorporated into Ada 95.

@ The reason for this omission is explained in Section G.1.1 of the Rationale for Ada 95 [3] which says A decision was made to abbreviate the Ada 95 packages by omitting the vector and matrix types and operations. One reason was that such types and operations were largely self-evident, so that little real help would be provided by defining them in the language. Another reason was that a future version of Ada might add enhancements for array manipulation and so it would be inappropriate to lock in such operations permanently.

@ The sort of enhancements that perhaps were being anticipated were facilities for manipulating arbitrary subpartitions of arrays such as were provided in Algol 68. These rather specialized facilities have not been added to Ada 2005 and indeed it seems most unlikely that they would ever be added. The second justification for omitting the vector and matrix facilities of 13813 thus disappears.

@ In order to overcome the objection that everything is self-evident we have taken the approach that we should further add some basic facilities that are commonly required, not completely trivial to implement, but on the other hand are mathematically well understood.

@ So the outcome is that Ada 2005 includes almost everything from 13813 plus subprograms for

@ A small number of operations that were not related to linear algebra were removed (such as raising all elements of a matrix to a given power).

@ So Ada 2005 includes two new packages which are Ada.Numerics.Generic_Real_Arrays and Ada.Numerics.Generic_Complex_Arrays. It would take too much space to give the specifications of both in full so we give just an abbreviated form of the real package in which the specifications of the usual operators are omitted thus 

  1        generic
  2                type Real is digits <>;
  3        package Ada.Numerics.Generic_Real_Arrays is
  4                pragma Pure (Generic_Real_Arrays);
  5                -- Types
  6                type Real_Vector is array (Integer range <>) of Real'Base;
  7                type Real_Matrix is array (Integer range <>, Integer range <>) of Real'Base;
  8                -- Real_Vector arithmetic operations
  9                ... -- unary and binary "+" and "–" giving a vector
 10                ... -- also inner product and two versions of "abs" – one returns a vector and the
 11                ... -- other a value of Real'Base
 12                -- Real_Vector scaling operations
 13                ... -- operations "*" and "/" to multiply a vector by a scalar and divide a vector by a scalar
 14                -- Other Real_Vector operations
 15                function Unit_Vector (Index : Integer; Order : Positive; First : Integer := 1) return Real_Vector;
 16                -- Real_Matrix arithmetic operations
 17                ... -- unary "+", "–", "abs", binary "+", "–" giving a matrix
 18                ... -- "*" on two matrices giving a matrix, on a vector and a matrix giving a vector,
 19                ... -- outer product of two vectors giving a matrix, and of course
 20                function Transpose (X : Real_Matrix) return Real_Matrix;
 21                -- Real_Matrix scaling operations
 22                ... -- operations "*" and "/" to multiply a matrix by a scalar and divide a matrix by a scalar
 23                -- Real_Matrix inversion and related operations
 24                function Solve (A : Real_Matrix; X : Real_Vector) return Real_Vector;
 25                function Solve (A, X : Real_Matrix) return Real_Matrix;
 26                function Inverse (A : Real_Matrix) return Real_Matrix;
 27                function Determinant (A : Real_Matrix) return Real'Base;
 28                -- Eigenvalues and vectors of a real symmetric matrix
 29                function Eigenvalues (A : Real_Matrix) return Real_Vector;
 30                procedure Eigensystem (A : in Real_Matrix;
 31                Values : out Real_Vector; Vectors : out Real_Matrix);
 32                -- Other Real_Matrix operations
 33                function Unit_Matrix (Order : Positive; First_1, First_2 : Integer := 1) return Real_Matrix;
 34        end Ada.Numerics.Generic_Real_Arrays;

@ Many of these operations are quite self-evident. The general idea as far as the usual arithmetic operations are concerned is that we just write an expression in the normal way as illustrated in the Introduction. But the following points should be noted.

@ There are two operations "abs" applying to a Real_Vector thus 

  1        function "abs" (Right : Real_Vector) return Real_Vector;
  2        function "abs" (Right : Real_Vector) return Real'Base;

@ One returns a vector each of whose elements is the absolute value of the corresponding element of the parameter (rather boring) and the other returns a scalar which is the so-called L2-norm of the vector. This is the square root of the inner product of the vector with itself or v (Sxixi) – or just v (xixi) using the summation convention (which will be familiar to those who dabble in the relative world of tensors). This is provided as a distinct operation in order to avoid any intermediate overflow that might occur if the user were to compute it directly using the inner product "*".

@ There are two functions Solve for solving one and several sets of linear equations respectively. Thus if we have the single set of n equations 

  1        Ax = y

@ then we might write 

  1        X, Y : Real_Vector (1 .. N);
  2        A : Real_Matrix (1 .. N, 1 .. N);
  3        ...
  4        Y := Solve (A, X);

@ and if we have m sets of n equations we might write 

  1        XX, YY : Real_Matrix (1 .. N, 1 .. M)
  2        A : Real_Matrix (1 .. N, 1 .. N);
  3        ...
  4        YY := Solve (A, XX);

@ The functions Inverse and Determinant are provided for completeness although they should be used with care. Remember that it is foolish to solve a set of equations by writing 

  1        Y := Inverse (A) * X;

@ because it is both slow and prone to errors. The main problem with Determinant is that it is liable to overflow or underflow even for moderate sized matrices. Thus if the elements are of the order of a thousand and the matrix has order 10, then the magnitude of the determinant will be of the order of 1030 . The user may therefore have to scale the data.

@ Two subprograms are provided for determining the eigenvalues and eigenvectors of a symmetric matrix. These are commonly required in many calculations in domains such as elasticity, moments of inertia, confidence regions and so on. The function Eigenvalues returns the eigenvalues (which will be non-negative) as a vector with them in decreasing order. The procedure Eigensystem computes both eigenvalues and vectors; the parameter Values is the same as that obtained by calling the function Eigenvalues and the parameter Vectors is a matrix whose columns are the corresponding eigenvectors in the same order. The eigenvectors are mutually orthonormal (that is, of unit length and mutually orthogonal) even when there are repeated eigenvalues. These subprograms apply only to symmetric matrices and if the matrix is not symmetric then Argument_Error is raised.

@ Other errors such as the mismatch of array bounds raise Constraint_Error by analogy with built-in array operations.

@ The reader will observe that the facilities provided here are rather humble and presented in a simple black-box style. It is important to appreciate that we do not see the Ada predefined numerics library as being in any way in competition with or as a substitute for professional libraries such as the renowned BLAS (Basic Linear Algebra Subprograms, see www.netlib.org/blas). Indeed our overall goal is twofold ? to provide commonly required simple facilities for the user who is not a numerical professional, ? to provide a baseline of types and operations that forms a firm foundation for binding to more general facilities such as the BLAS.

@ We do not expect users to apply the operations in our Ada packages to the huge matrices that arise in areas such as partial differential equations. Such matrices are often of a special nature such as banded and need the facilities of a comprehensive numerical library. We have instead striven to provide easy to use facilities for the programmer who has a small number of equations to solve such as might arise in navigational applications.

@ Simplicity is evident in that functions such as Solve do not reveal the almost inevitable underlying LU decomposition or provide parameters controlling for example whether additional iterations should be applied. However, implementations are advised to apply an additional iteration and should document whether they do or not.

@ Considerations of simplicity also led to the decision not to provide automatic scaling for the determinant or to provide functions for just the largest eigenvalue and so on.

@ Similarly we only provide for the eigensystems of symmetric real matrices. These are the ones that commonly arise and are well behaved. General nonsymmetric matrices can be troublesome.

@ Appropriate accuracy requirements are specified for the inner product and L2-norm operations.

@ Accuracy requirements for Solve, Inverse, Determinant, Eigenvalues and Eigenvectors are implementation defined which means that the implementation must document them.

@ The complex package is very similar and will not be described in detail. However, the generic formal parameters are interesting. They are 

  1        with Ada.Numerics.Generic_Real_Arrays, Ada.Numerics.Generic_Complex_Types;
  2        generic
  3                with package Real_Arrays is new Ada.Numerics.Generic_Real_Arrays (<>);
  4                use Real_Arrays;
  5                with package Complex_Types is new Ada.Numerics.Generic_Complex_Types (Real);
  6                use Complex_Types;
  7        package Ada.Numerics.Generic_Complex_Arrays is
  8        ...

@ Thus we see that it has two formal packages which are the corresponding real array package and the existing Ada 95 complex types and operations package. The formal parameter of the first is <> and that of the second is Real which is exported from the first package and ensures that both are instantiated with the same floating point type.

@ As well as the obvious array and matrix operations, the complex package also has operations for composing complex arrays from cartesian and polar real arrays, and computing the conjugate array by analogy with scalar operations in the complex types package. There are also mixed real and complex array operations but not mixed imaginary, real and complex array operations. Altogether the complex array package declares some 80 subprograms (there are around 30 in the real array package) and adding imaginary array operations would have made the package unwieldy (and the reference manual too heavy).

@ By analogy with real symmetric matrices, the complex package has subprograms for determining the eigensystems of Hermitian matrices. A Hermitian matrix is one whose complex conjugate equals its transpose; such matrices have real eigenvalues and are well behaved.

@ We conclude this discussion of the Numerics annex by mentioning one minute change regarding complex input–output. Ada 2005 includes preinstantiated forms of Ada.Text_IO.Complex_IO such as Ada.Complex_Text_IO (for when the underlying real type is the type Float), Ada.Long_ Complex_Text_IO (for type Long_Float) and so on. These are by analogy with Float_Text_IO, Long_Float_Text_IO and their omission from Ada 95 was probably an oversight.

Rationale for Ada 2005: Predefined library

@ENGRUSTOPBACKNEXT

6. Приложение численных данных

@ При разработке ada Numerics Rapporteur Group (Группа Докладчика Численных данных) определила какие возможности должны быть включены в Аду 95 непосредственно, какие должны быть помещены во вторичные стандарты, а что нужно оставить к творческому началу пользовательского сообщества.

@ Для Ады 83 были разработаны следующие вторичные стандарты:

@ Первые два (11430 и 11729) были включены в базовый язык. Элементарные функции (11430 (Sqrt, Sin, Cos и т.д)) оказались в пакете Ada.Numerics.Generic_Elementary_Functions в A 5.1, а примитивные функции (11729) стали различными атрибутами, такими как Floor, Ceiling, Exponent и Fraction в A 5.3. Оригинальные стандарты были отброшены.

@ Другие два стандарта, хотя первоначально и были разработаны как стандарт Ады 83 но они не были одобренны вподь до 1998.

@ Функциональные возможности 13814 были включены в приложение Численных данных ada в пакет Ada.Numerics.Generic_Complex_Elementary_Functions в G 1.2. Соответственно оригинальный стандарт теперь утратил силу.

@ Однако, ситуация относительно 13813 не была настолько ясна. Он покрывал четыре области
  1. пакет комплексных типов, включая различные арифметические операции с комплексными числами;
  2. пакет массивов реальных чисел покрывающий и векторы и матрицы;
  3. пакет массивов комплексных чисел покрывающий и векторы и матрицы;
  4. пакет ввода - вывода комплексных чисел.

@ Первый из них был включен в приложение Численных данных ada как пакет Ada.Numerics.Generic_Complex_Types в G 1.1, последний так же стал пакетом Ada.Text_IO.Complex_IO в G 1.3. Однако, пакеты реальных и комплексных массивовне не были включены в Аду 95.

@ Причина этого вычеркивания объяснена в Секции G 1.1 Разъяснения для ada [3] где говорится, что решение было принято чтобы сократить пакеты ada, опуская векторные и матричные типы и операции. Одна из причин состояла в том, что такие типы и операции были в значительной степени самоочевидны, ??? так чтобы небольшая реальная справка была предоставлена, определяя их в языке ???. Другая причина была в том, что будущая версия Ады могла бы добавить расширения для манипуляции массивами и, таким образом, было бы неуместно блокировать такие операции надолго.

@ Одно из расширений которое ожидалось было средство для манипулирования произвольным подразделением массивов как в Алголе 68. Эти скорее узкоспециализированные средства так и не были добавлены в Аду 2005, и весьма сомнительно их добавление в обозримом будущем. Вторая причина для того чтобы опустить вектора и матричные средства 13813 таким образом исчезает.

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

@ Таким образом, в результате Ада 2005 включает почти всё из 13813 плюс подпрограммы для:

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

@ Так Ада 2005 включает два новых пакета Ada.Numerics.Generic_Real_Arrays и Ada.Numerics.Generic_Complex_Arrays. Здесь мы даем только сокращенную форму реального пакета в котором спецификации обычных операторов опущены (т.к. полная спецификация заняла бы слишком много места):

 
  1        generic
  2                type Real is digits <>;
  3        package Ada.Numerics.Generic_Real_Arrays is
  4                pragma Pure (Generic_Real_Arrays);
  5                -- Types
  6                type Real_Vector is array (Integer range <>) of Real'Base;
  7                type Real_Matrix is array (Integer range <>, Integer range <>) of Real'Base;
  8                -- Real_Vector arithmetic operations
  9                ... -- unary and binary "+" and "–" giving a vector
 10                ... -- also inner product and two versions of "abs" – one returns a vector and the
 11                ... -- other a value of Real'Base
 12                -- Real_Vector scaling operations
 13                ... -- operations "*" and "/" to multiply a vector by a scalar and divide a vector by a scalar
 14                -- Other Real_Vector operations
 15                function Unit_Vector (Index : Integer; Order : Positive; First : Integer := 1) return Real_Vector;
 16                -- Real_Matrix arithmetic operations
 17                ... -- unary "+", "–", "abs", binary "+", "–" giving a matrix
 18                ... -- "*" on two matrices giving a matrix, on a vector and a matrix giving a vector,
 19                ... -- outer product of two vectors giving a matrix, and of course
 20                function Transpose (X : Real_Matrix) return Real_Matrix;
 21                -- Real_Matrix scaling operations
 22                ... -- operations "*" and "/" to multiply a matrix by a scalar and divide a matrix by a scalar
 23                -- Real_Matrix inversion and related operations
 24                function Solve (A : Real_Matrix; X : Real_Vector) return Real_Vector;
 25                function Solve (A, X : Real_Matrix) return Real_Matrix;
 26                function Inverse (A : Real_Matrix) return Real_Matrix;
 27                function Determinant (A : Real_Matrix) return Real'Base;
 28                -- Eigenvalues and vectors of a real symmetric matrix
 29                function Eigenvalues (A : Real_Matrix) return Real_Vector;
 30                procedure Eigensystem (A : in Real_Matrix;
 31                Values : out Real_Vector; Vectors : out Real_Matrix);
 32                -- Other Real_Matrix operations
 33                function Unit_Matrix (Order : Positive; First_1, First_2 : Integer := 1) return Real_Matrix;
 34        end Ada.Numerics.Generic_Real_Arrays;

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

@ Есть две операции "abs" обрабатывающие Real_Vector следующим образом:

 
  1        function "abs" (Right : Real_Vector) return Real_Vector;
  2        function "abs" (Right : Real_Vector) return Real'Base;

@ Первая возвращает вектор, каждый элемент которого - абсолютное значение соответствующего элемента параметра (ничего необычного), а другой возвращает скаляр, который является так называемой L2-нормой вектора. Это - квадратный корень внутреннего продукта вектора с собой или v (Sxixi) - или только v (xixi) использование соглашения суммирования (который знаком тем, кто балуется относительным миром тензоров). Для этого предоставляется отличная операция, которая позволяет избежать любого промежуточного переполнения, которое могло бы произойти, если бы пользователь вычислял его непосредственно используя ??? внутренний продукт "*" ???.

@ Есть две функции Solve для того, чтобы решить соответственно одну или несколько систем линейных уравнений. Таким образом, если у нас есть система из n уравнений:

 
  1        Ax = y

@ тогда мы можем написать:

 
  1        X, Y : Real_Vector (1 .. N);
  2        A : Real_Matrix (1 .. N, 1 .. N);
  3        ...
  4        Y := Solve (A, X);

@ и если мы имеем m систем из n уравнений, тогда мы можем написать:

 
  1        XX, YY : Real_Matrix (1 .. N, 1 .. M)
  2        A : Real_Matrix (1 .. N, 1 .. N);
  3        ...
  4        YY := Solve (A, XX);

@ Функции Inverse и Determinant предоставлены для функциональной полноты, хотя они должны использоваться осторожно. Ибо, весьма глупо решать систему уравнений следующим образом:

 
  1        Y := Inverse (A) * X;

@ потому что это весьма медленно и склонно к ошибкам. Основная проблема с Determinant состоит в том, что она склонна к переполннению и потере порядка даже для умеренных размеров матриц. Так, если количество элементов будет иметь порядок 1000, а у матрицы порядок 10, то величина детерминанта будет иметь порядок 1030. Пользователю, вероятно, поэтому придется масштабировать данные.

@ Две подпрограммы предоставлены для того, чтобы определить собственные значения и собственные векторы симметричной матрицы. Они обычно требуются во многих вычислениях в доменах, таких как адаптационная способность, моменты инерции, области уверенности и так далее. Функция Eigenvalues возвращает собственное значение (которое будет неотрицательным) как вектор в порядке убывания. Процедура Eigensystem вычисляет и собственные значения и векторы; параметр Values - то же самое, поскольку полученное, вызывая функцию Eigenvalues и параметр Vectors является матрицей, столбцы которой - соответствующие собственные векторы в том же самом порядке. Собственные векторы взаимно orthonormal (то есть, длины модуля и взаимно ортогональны), даже когда есть повторенные собственные значения. Эти подпрограммы применяются только к симметричным матрицам и если матрица не симметрична тогда возбуждается исключение Argument_Error.

@ Другие ошибки, такие как несоответствие границ массива поднимают исключение Constraint_Error по аналогии со встроенными операциями над массивами.

@ Читатель заметит, что средства, предоставленные здесь, довольно скромны и представлены в простом стиле черного ящика. Важно понять, что мы не видим предопределенную библиотеку численных данных как альтернативу какой-нибудь из профессиональных библиотек, таких как известная BLAS (Основные Линейные Подпрограммы Алгебры, см. www.netlib.org/blas). Действительно, наша полная цель является двоякой: 1) предоставить обычно требуемые простые средства пользователю, который не является профессионалом в численных методах; 2) обеспечить базовую линию типов и операций, которые обеспечили бы основу для перехода к более мощными средствами, такими как BLAS.

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

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

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

@ Так же мы только предусматриваем eigensystems симметричных реальных матриц. Они чаще встречаются и обычно хорошо ведутся себя. В отличие от них с общими несимметричными матрицами может быть масса проблем.

@ Соответствующие требования точности определены для внутреннего продукта и операций L2-norm.

@ Требования точности для Solve, Inverse, Determinant, Eigenvalues и Eigenvectors - определяются реализацией, что означает, что реализация должна зарегистрировать их.

@ Пакет Complex очень похож и не будет описан подробно. Однако, универсальные формальные параметры интересны. Они следующие:

 
  1        with Ada.Numerics.Generic_Real_Arrays, Ada.Numerics.Generic_Complex_Types;
  2        generic
  3                with package Real_Arrays is new Ada.Numerics.Generic_Real_Arrays (<>);
  4                use Real_Arrays;
  5                with package Complex_Types is new Ada.Numerics.Generic_Complex_Types (Real);
  6                use Complex_Types;
  7        package Ada.Numerics.Generic_Complex_Arrays is
  8        ...

@ Таким образом, мы видим, что здесь есть два формальных пакета, которые являются соответственно пакетом реальных массивов и существующим в Аде 95 пакетом комплексных типов и операций. Формальный параметр первого <>, а второго Real, который экспортируется из первого пакета, что гарантирует что оба иллюстрируются с одним и тем же типом с плавающей запятой.

@ Так же как очевидный массив и матричные операции, у комплксного пакета также есть операции для того, чтобы составить комплексные массивы из декартовых и полярных реальных массивов, и вычислить сопряженный массив по аналогии со скалярными операциями в пакете комплексных типов. Там также смешаны реальные и комплексные операции над массивами, но не смешиваются мнимые, реальные и комплексные операции над массивами. В целом пакет комплексных массивов объявляет приблизительно 80 подпрограмм (в пакете реальных массивов их приблизительно 30), и добавление мнимых операций над массивами сделали бы пакет весьма громоздким (а справочное описание слишком тяжёлым).

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

@ Завершая это обсуждение приложения Численных данных упомянем одно мелкое изменение относительно комплексного ввода - вывода. Ада 2005 включает предиллюстрированную примерами форму Ada.Text_IO.Complex_IO, такую как Ada.Complex_Text_IO (для случая, когда основной реальный тип - Float), Ada.Long_ Complex_Text_IO (для типа Long_Float) и так далее. Они аналогичны Float_Text_IO, Long_Float_Text_IO и их исключение из ada в своё время теперь считается оплошностью.

@ ENG RUS

TOP BACK NEXT

2010-10-24 00:26:58

. .