Я пытаюсь разработать программу на C для преобразования файла разреженной матрицы в плотную матрицу. Из того, что я прочитал, лучшим подходом было бы использование связанных списков, но у меня нет опыта работы с ними, и я не нашел хорошего онлайн-ресурса, объясняющего эту тему. Я не ищу быстрого решения, а скорее веб-сайт или текстовый источник, который может объяснить, как работает процесс, чтобы я мог применить его к этому проекту. Какие ресурсы я видел, предлагают использовать три массива для обработки значений в матрице (строка, столбец и отдельное значение) и два массива для вектора (один для строки, другой для столбца). Спасибо!
Преобразование разреженной матрицы в C
comment
В каком формате данные в исходном файле.
- person Jonathan Wood schedule 01.05.2011
comment
Входной файл не будет содержать лишнего форматирования и будет строго последовательно заполнен необходимыми значениями. Первые два значения в матричном файле будут обозначать размерности с точки зрения строк и столбцов, а остальные значения будут необходимыми данными. Например, если бы у меня была матрица 10x10, первые два значения были бы 10 и 10, за которыми следуют еще 100 элементов, которые будут использоваться в качестве данных. Я должен преобразовать разреженную матрицу в плотно заполненную матрицу, чтобы я мог выполнить умножение матрицы на вектор, поэтому и матрица, и вектор должны подвергнуться преобразованию.
- person Strata schedule 01.05.2011
comment
Однако я уже разработал алгоритм умножения, так что с этим аспектом покончено. После начальных двух значений остальная часть файла будет перечислять значения в последовательности, но после преобразования они будут сохранены в одномерном массиве. Извините, если это неясно, так как концепция все еще очень абстрактна для меня.
- person Strata schedule 01.05.2011
comment
Почему связанные списки? Разве основная процедура не состоит в том, чтобы выделить большой массив для представления плотной матрицы, а затем прочитать представление разреженной матрицы, заполнив различные элементы массива плотной матрицы?
- person Oliver Charlesworth schedule 01.05.2011
comment
Для этого конкретного проекта мне нужно максимизировать производительность и эффективное время обработки, гарантируя, что алгоритм выполняет как можно меньше вычислений. Таким образом, связанные списки являются предпочтительным методом работы с матрицей в этой ситуации. Я недостаточно знаю о процессе, чтобы дать лучший ответ, к сожалению.
- person Strata schedule 01.05.2011
comment
@Strata: это не имеет смысла. Плотная матрица по определению представляет собой большой массив. Как связанные списки вписываются в картину? Кто вам сказал, это?
- person Oliver Charlesworth schedule 01.05.2011
comment
@Strata: я здесь с @Oli. Если вы конвертируете в плотный массив, то просто загружайте данные из файла прямо в такой массив. Вы можете использовать связанные списки как один из способов реализации разреженного массива. Но, исходя из вашего вопроса, это не то, что вы делаете.
- person Jonathan Wood schedule 01.05.2011
Ответы (2)
Указанный формат файла предназначен для плотной матрицы. Матрица 10x10 из 100 элементов плотная. Разреженная матрица имеет менее n*m элементов, и предполагается, что все «отсутствующие» элементы равны 0. Смысл такого подхода в том, что матрицы, которые почти полностью равны нулю (что происходит во многих приложениях), будут использовать меньше Космос. Но использование формата разреженной матрицы для хранения плотной матрицы потребует гораздо больше места, чем простой массив.
Один распространенный формат файла разреженной матрицы называется MatrixMarket, и он очень похож на то, что вы описали. Первая строка имеет три значения: # строк, # столбцов, # ненулевых элементов (называемых nnz). Тогда у вас есть nnz строк фактических элементов в триплете: (row #) (column #) (value) Если ваша разреженная матрица имеет аналогичный формат, вам не нужна разреженная матрица в памяти. Просто отсканируйте значения и заполните свой плотный массив напрямую.
Если вы хотите иметь в памяти разреженную матрицу, есть несколько вариантов ее хранения. Триплеты проще всего, и это просто версия файла MatrixMarket в памяти. 3 массива или 1 массив структур. Наиболее распространенной структурой для операций линейной алгебры являются сжатые разреженные столбцы (CSC) или сжатые разреженные строки (CSR). Я позволю вам посмотреть это, но если вы хотите поиграть с реализацией C, вам следует взглянуть на CSparse. Точно так же MatLAB хранит разреженные матрицы, Тим был одним из тех, кто написал эту часть MatLAB.
person
Adam
schedule
18.05.2011
Похоже, что связанный список может быть не тем, что вы ищете, но этот сайт предлагает довольно всеобъемлющий учебник по этому вопросу. Это может помочь пролить свет на то, подходит ли это для вашей проблемы... Удачи!
person
tpm1510
schedule
09.05.2011
