Nano Hash - криптовалюты, майнинг, программирование

Решение Ax=b, где A слишком велико для хранения в одном массиве

Проблема: A квадратный, полный ранг, разреженный и полосатый. В нем слишком много элементов для хранения в виде одной матрицы в Matlab (как минимум ~4,6*1018 и в идеале ~1040, оба из которых превышают максимальный размер массива. РЕДАКТИРОВАТЬ: A хранится как разреженное, и проблема не в ограниченной памяти, а в ограниченном количестве элементов). Поэтому я должен хранить его как набор меньших массивов (строки/диагонали/столбцы/блоки).

Ищу: способ решения Ax=b, где A задан как набор меньших массивов. В идеале в Matlab, но не обязательно.
В качестве альтернативы, если не в Matlab: может быть, есть программа, которая может хранить и решать такую ​​​​большую А?

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

p.s. Система 64-битная.

Спасибо всем!

matlab matrix equation-solving scientific-computing
14.09.2014

  • Определили вашу матрицу как обычную матрицу? Не явно как sparse? Последнее должно сэкономить вам много памяти. Для решения: эта статья , вероятно, полезно. Я никогда не использовал разреженные матрицы и не могу вам больше помочь, но, конечно, другие могут;) 14.09.2014
  • sparse также имеет ограничения по размеру. Проверьте второй выходной аргумент computer, он возвращает максимальное количество элементов, которые можно проиндексировать. [~,maxsize]=computer. Я не привожу их здесь, потому что они зависят от вашей версии Matlab, но, насколько я знаю, ни одна версия не поддерживает 4,6 * 10 ^ 18 элементов. 14.09.2014
  • Вам нужно найти решатель, который будет использовать указатель/дескриптор функции, а не массив, хранящийся в памяти. Я просто быстро посмотрел, но ничего не нашел. Однако я уверен, что такой существует. При этом я подозреваю, что у вас будут проблемы с точностью с таким количеством элементов независимо от решателя. 15.09.2014
  • AnonSubmitter85: Звучит многообещающе, у вас есть какие-нибудь ключевые слова или направления поиска для такого решателя? 15.09.2014
  • @ООО. Извините за комментарий ранее, я не уловил, что ограничивающим фактором было количество элементов, а не память. Как предположил Анон, для системы такого размера вам придется найти какие-то специальные алгоритмы. Для начала вы можете ознакомиться с этим методом Fast Inverse, используя Вложенное рассечение. Читать долго, но многообещающе. Я не знаю, есть ли готовый решатель, использующий этот алгоритм. 15.09.2014
  • @OOO, о каком количестве элементов ты говоришь? Количество ненулевых или общее количество элементов полной матрицы? Каков номер строки соответствующей полной матрицы? Когда вы сказали N диагоналей, каково значение N? 09.07.2015

Ответы:


1

Неиспользование Matlab позволит вам хранить большие массивы. ROOT – это платформа с открытым исходным кодом, разработанная в ЦЕРНе, которая имеет интерфейсы C++ и Python и различные решатели. Он также способен обрабатывать огромные наборы данных и имеет множество инструментов визуализации и анализа.

Если вы заинтересованы в написании C или Fortran, BLAS (базовые подпрограммы линейной алгебры) и CBLAS будут хорошие варианты. Существует множество проприетарных и открытых реализаций BLAS, которые должны быть доступны для большинства дистрибутивов Linux/UNIX. Есть также множество примеров, показывающих, как использовать подпрограммы BLAS в коде C и Fortran, доступных в Интернете.

08.07.2015

2

Если у вас есть доступ к MATLAB Parallel Computing Toolbox вместе с MATLAB Distributed Computing Server, вы можете хранить A как distributed array, другими словами, один массив, элементы которого распределены по памяти нескольких машин в кластере. Вы можете вызвать команду обратной косой черты MATLAB непосредственно для распределенного массива, и MATLAB выполнит распараллеливание за вас.

14.09.2014
  • Звучит интересно спасибо! Я просмотрел их и не смог найти следующее: Знаете ли вы, могут ли распределенные массивы содержать больше элементов, чем обычные массивы? Я думал, проблема в том, что индекс элементов ограничен. Преодолевают ли распределенные массивы это? 15.09.2014
  • @OOO Распределенный массив может содержать больше элементов, чем обычный массив, если ваши разные рабочие процессы находятся на отдельных машинах (таким образом, вы фактически увеличиваете общую доступную память). В противном случае распределение работы по нескольким ядрам одной и той же машины даст вам только время обработки, а не дополнительную память. 15.09.2014
  • @Хоки Спасибо. Просто чтобы убедиться: моя проблема не в памяти, а в количестве элементов (т.е. пустая разреженная матрица имеет ограниченный размер, как на этой странице: mathworks.com/matlabcentral/answers/), распределенный массив на нескольких машинах будет иметь увеличить количество элементов? 15.09.2014

    • 3

    Я хотел поместить это как комментарий, но я думаю, что лучше указать это как ответ. У вас серьезная проблема. Проблема не только в индексации, но и в памяти: 4,6x10^18 — это огромно. Это 4,6 экза элемента. Если вы храните их как настоящую одинарную точность, вам потребуется 4x4,6 экзабайта памяти. Насколько мне известно, компьютера с такой огромной памятью еще не существует. Вам нужно будет собрать всю память (жесткий диск, а не оперативную память) значительной части всех компьютеров в мире для хранения такой матрицы. Подумай об этом. Переход к 10^40 элементам пока практически нецелесообразен. На ваших 64-битных компьютерах 64-битное адресное пространство может адресовать 4,6x10^18 элементов. 64-битный адрес (или целое число) позволяет напрямую индексировать 2 ^ 64 элемента, что составляет примерно 16x10 ^ 18. Так что вы должны подумать дважды.

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

    09.07.2015
  • ОП заявил, что это разреженная матрица. 09.07.2015
  • @rlbond Я не понимаю твоей точки зрения. Можете ли вы объяснить немного? 09.07.2015
  • @rlbond, я до сих пор не понимаю. У меня есть некоторый опыт работы с разреженными матрицами. Можете ли вы указать на что-то, что я сказал, что противоречит тому, что сказал ООО, или противоречит разреженным матрицам? 09.07.2015
  • OP сказал, что их матрица в основном состоит из нулей, они не используют память в разреженной матричной структуре данных. 09.07.2015
  • Теперь я тебя понял. ООО также сказали, что их матрица уже хранится как разреженная. Из этого я сделал вывод, что он говорил о числе, отличном от нуля. Я помещаю комментарий, чтобы попросить его разъяснения. 09.07.2015
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..