Политика и методы кэширования для матриц

Question

Как объяснялось ранее, я сейчас работаю над небольшой библиотекой линейной алгебры, которую можно использовать в личном проекте. Матрицы реализованы как векторы C ++, и присваивание элементов (a (i, j) = v;) делегируется присваиванию элементам вектора. Для моего проекта мне нужно будет решить тонны систем квадратного уравнения, и для этого я применил LU-факторизацию (Гауссово исключение) для квадратных матриц. В текущей реализации я избегаю пересчитывать каждый раз факторизацию LU путем кэширования матриц L и U, проблема заключается в том, что, поскольку я делегирую присваивание элемента вектору, я не могу найти способ сказать, если матрица меняется и нужно ли пересчитывать факторизацию. Есть идеи, как это решить?

Спасибо

Answer 1

template<class T>
class matrix {
public:
    class accessor {
    public:
        accessor(T& dest, matrix& parent) : dest(dest), parent(parent) { }
        operator T const& () const { return dest; }
        accessor& operator=(T const& t) { dest = t; parent.invalidate_cache(); return *this; }
    private:
        T& dest;
        matrix& parent;
    };

    // replace those with actual implementation..
    accessor operator()(int x, int y) {
        static T t; return accessor(t, *this);
    }
    T const& operator()(int x, int y) const {
        static T t; return t;
    }

private:
    void invalidate_cache() { cout << "Cache invalidated !!\n"; }
    vector<T> impl;
};

спасибо за помощь в ## iso-c ++ @ irc.freenode.net за некоторые полезные исправления

Answer 2

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

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

Примером реализации может быть:

class Matrix {
public:
    Matrix() : hasChanged(false) {}

    double setElement(int i, int j, double value) {
        innerStorage[i][j] = value;
        hasChanged = true;
    }

    double getElement(int i, int j) {
        return innerStorage[i][j];
    }

    void clearHasChangedFlag() {
        hasChanged = false;
    }

private:
    vector<vector<double> > innerStorage;
    bool hasChanged;
}

Answer 3

Как насчет сохранения полной скрытой копии Матрицы, использованной с последней факторизацией LU, и проверки ее за O (n * m) раз перед повторным выполнением? Ужасно, но может работать.

Answer 4

Варианты setElement и getElement, предложенные Фредериком, были опцией, но использовать ее слишком скучно. Я хочу получить доступ к (i, j) при чтении и записи с одинаковым синтаксисом, не беспокоясь о том, изменяю ли я матрицу или нет. Вероятно, лучшее, что можно сделать, это позволить пользователю изменить Матрицу и передать ему ответственность за пересчет факторизации LU, когда он сочтет это необходимым. И все же это будет очень скучно.

Answer 5

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

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

Вы можете попробовать заводской интерфейс для матричных преобразований / разложений. Это простой метод, который принимает матрицу и возвращает (разложенную) матрицу. Вы сохраняете свою оригинальную матрицу таким образом; возвращаемое значение является новым экземпляром. Вы можете изменить оригинал и затем передать его на завод, чтобы пересчитать разложение LU. Это стоит вашей памяти, что может быть проблемой для очень больших матриц.

На Java я бы написал так:

public interface MatrixDecomposition
{  
    Matrix decompose(Matrix original);
}

В C ++ это была бы чисто виртуальная функция. (Слишком долго - я не могу вспомнить синтаксис.)

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

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