Интерфейс Прикладных Программ (ИПП).

Эта страничка отражает текущее понимание Интерфейса Прикладных Программ (ИПП) интервальной библиотеки. На английском языке это называется Application Program Interface (API). По тем пунктам, где еще нет полного согласия, кратко приводятся альтернативные варианты, а детальное обсуждение идет на форуме.

При составлении API руководствуемся следующими приоритетами требований.

Интервалы неизменямы (immutable).

Скаляры

Язык C приучил программиста-численника, что параметры функции (в том числе типа double) передаются как значения, хотя в Fortran это было не так. Поэтому он будет примерно так же работать с параметрами типа интеравал - например свободно переприсваивать им в теле функции.

 double f(double x) {
     x = Math.exp(x);
     return (x - 1)/(x + 1);
  }
 
  x = 0;
  print f(x) + x; // Ожидаем 0

В языке Java нет структур, передаваемых по значению. Есть, объекты, передаваемые по ссылке. Если сделать их mutable, то есть разрешить переприсваивать полям этих объектов, возможны ошибки вида:

 Interval f(Interval x) {
    x.assign(x.exp());
    return x.minus(Interval.ONE).divide(x.plus.Interval.ONE);
 }
 
 x.assign(Interval.ZERO);
 print f(x).plus(x); // Получается [1,1]

Если же объекты immutable, то таких ошибок можно избежать.

 Interval f(Interval x) {
   x = x.exp();
   return x.minus(Interval.ONE).divide(x.plus.Interval.ONE);
 }
 
 x = Interval.ZERO;
 print f(x).plus(x); // Получается [0,0]
     

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

В списке приоритетов понятность важнее производительности. Следовательно принимаем, что Interval неизменяем (immutable).

Вектора и матрицы.

Что касается матриц, то вопрос mutable - immutable не так ясен.

Если посмотреть на другие математические Java библиотеки, то встречаются оба варианта

• В JScience вектора и матрицы полностью immutable.
• В Apache Commons Math основные операции возвращают новые вектора или матрицы, но есть методы, которые модифицируют вектора или матрицы.

Гибкость и расширяемость в смысле различных интервальных арифметик.

Была речь о реализации следующих интервальных арифметик:

• IR - классическая арифметика с интервалами вида [l,u], где l и u - рациональные числа, l <= u
• IR* - расширенная интервальная арифметика, l может быть -Infinity, а u может быть +Infinity
• KR - арифметика Каухера с интервалами [l,u], где нет ограничения l <= u .
• комплексная арифметика с интервалами типа брус [a,b] + I*[c,d]
• комплекcная арифметика с интервалами типа диск |z - z_0| <= r
• Twin интервальная арифметика - не планируется в ближайшем будущем

Если говорить о всех этих арифметиках словами алгебры, то все эти алгебры имеют одинаковую сигнатуру - то есть одинаковый набор операций.

Так как все интервальные арифметики имеют общую сигнатуру, целесообразно записать эту сигнатуру в виде Java интерфейса

 interface Interval< I extends Interval< I>> {
    I negate();
    I add(I y);
    ....
    I exp();
    I sqr();
    I sqrt();
    ....
 }

Представляется, что различные интервальные аоифметики будут реализованы независимыми между собой классами. Все они будут реализовывать интерфейс Interval< I> примерно таким образом.

  class IntervalRealClassic implements Interval< IntervalRealClassic> {}
  class IntervalRealKaucher implements Interval< IntervalRealKaucher> {}
  class IntervalComplexBox  implements Interval< IntervalComplexBox> {}

При таком подходе и при включенной опции -Xlint:unchecked компилятор будет ругаться на попытки смешать объекты из разных арифметик:

  IntervalRealClassic x, y;
  IntervalRealKaucher kx, ky;
  x.add(y); // верно
  kx.add(ky); // верно
  x.add(ky); // неверно

Можно описывать generic-функции, работающие с произвольными арифметиками:

 <I extends Interval> I hypot(I x, I y) {
     return x.sqr().add(y.sqr()).sqrt();  
 }
 x = hypot(x, y); // верно
 kx = hypot(kx, ky); // верно
 x = hypot(x, ky); // неверно
 kx = hypot(x, y);; // неверно

Наращивание функционала - разреженные матрицы

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

Совместимость с другими библиотеками

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

Примеры того, что могло бы быть полезно:

• разреженные матрицы из JScience и Apache Commons Math;
• Пакет автоматического дифференцирования из Apache Commons Nabla. Он интересен тем, что он берет обычную функции над double, разбирает ее bytecode и преобразует в программу, которая строит дерево разбора выражений;
• Управление памятью и контекстом из Javoltion

По способу использования чужих библиотек разные мнения:

• Читать чужие алгоритмы и программировать их заново;
• Копировать файлы и фрагменты кода;
• Использовать внешние jar файлы.

Этот вопрос требует обсуждения на форуме.

Гибкость в отношении базовых типов и связанных с ними политик округления

Разнообразные интервалы ( вещественные, комплексные, каухеровы) в конечном счете представляются несколькими вещественными числами. Это могут быть нижний и верхний концы вещественного интервала , или действительная и мнимая компоненты центра и радиус комплексного интервала и т.д. Естественно в API должны быть как конструкторы, создающие интервал по нескольким вещественным числам, так и функции-getter'ы, возвращающие вещественные характеристики интервала. Разные реализации могут использовать разные представления вещественных характеристик тнтервала: примитивные типы float, double, объекты BigInteger, BigDecimal или специально спроектированные классы.

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

Далее обсуждается множество вещественных значений, представимых базовыми типами. Затем предлагается набор Java-классов, представляющих базовые типы.

Множество значений - рациональные числа

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

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

АPI для разных интервальных арифметик

Далее рассматриваются варианты принципов организации API для разных интервальных арифметик

• Классической интервальная арифметика
• Арифметика Каухера
• Комплексные интервальные арифметики

Вопросы для решения

1. Сигнатурный интерфейс Interval< T> и независимые реализации для разных арифметик, либо подалгебры представлены как подинтерфейсы
2. mutable или immutable вектора и матрицы
3. Степень совместимости с другими библиотеками