VPF::Перемножение матриц - Форум программистов

hello19

Дата 21.7.2011, 10:09 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 42
Регистрация: 13.7.2011

Репутация: нет
Всего: нет

Привет всем!
Нужен код для перемножения матрицы и столбца за минимально возможное время.
Порядок матрицы ( и столбца ) огромен - около 100000. Помогите найти оптимальный код!
Ищу уже 2 день... что-то безрезультатно как то(((

bsa

Дата 21.7.2011, 11:14 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Это не подходит? http://www.boost.org/doc/libs/1_47_0/libs/...s/doc/index.htm

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Silent

Дата 21.7.2011, 12:32 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 1
Всего: 9

эм... а в чем проблема?
либо берем стандартную библиотеку (atlas, blas, gotoblas, intel mkl...), либо пишем ручками сами. Самописная простейшая версия на моем i3 без учета ввода-вывода работает 2 минуты на одном ядре, так что 100000 - мне не кажется слишком суровым порядком, можно предположить, что общее время будет равно времени чтения файла с данными с диска

W4FhLF

Дата 21.7.2011, 12:55 (ссылка)

(нет голосов)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 2
Всего: 121

Каков размер матрицы по двум измерениям? Матрица разряженая или плотная? И частью какой задачи является данная операция?

Классическое произведение матрица-вектор самая популярная операция в линейной алгебре, реализаций вагон и маленькая тележка, в том числе в открытых библиотеках которые уже перечислили.

--------------------

"Бог умер" © Ницше
"Ницше умер" © Бог

baldina

Дата 21.7.2011, 12:57 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 15
Всего: 101

Цитата(hello19 @ 21.7.2011, 10:09

)

Порядок матрицы ( и столбца ) огромен

матрица поди разреженная? как представлена?

Добавлено через 2 минуты и 34 секунды

Цитата(Silent @ 21.7.2011, 12:32

)

2 минуты на одном ядре

это медленно. решение системы уравнений такого порядка для сильно разреженной матрицы (например, МКЭ) идет быстрее

Silent

Дата 22.7.2011, 11:31 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 1
Всего: 9

Цитата

Добавлено через 2 минуты и 34 секунды
Цитата(Silent @ 21.7.2011, 12:32 Найти цитируемый пост)
2 минуты на одном ядре

это медленно. решение системы уравнений такого порядка для сильно разреженной матрицы (например, МКЭ) идет быстрее

baldina, не выдирайте цитату из контекста. 2минуты = (i3+HT) / 4,

Цитата

Самописная простейшая версия

, с никакими оптимизациями. Поглядите на как люди алгоритм ускоряли, "в лоб" 600с и "финал" 7,52с - небо и земля, ~100х
Я всего лишь хотел показать, что задача решается за разумное время, и чтобы автор топика не боялся этой "зубастой" задачи.

baldina

Дата 22.7.2011, 13:01 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 15
Всего: 101

Цитата(Silent @ 22.7.2011, 11:31

)

Поглядите на как люди алгоритм ускоряли

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

Silent

Дата 27.7.2011, 11:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 1
Всего: 9

Автор топика молчит и не появляется ))
Предлагаю первый вариант "а-ля-блочное-решение", чтобы было от чего отталкиваться:

Код


#include <stdio.h>
#include <windows.h>

const int N = 100000;
int a[N];    //row matrix
int v[N];    //vector
int ans[N];    //answer

void init()
{
    HANDLE fin = CreateFile ( TEXT ( "vector.dat" ), GENERIC_READ, 0, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL );
    
    if ( fin == INVALID_HANDLE_VALUE ) {
        fprintf ( stderr, "ERROR: File %s could not be opened\n", "vector.dat" );
        exit ( 1 );
    }
    DWORD size_read;
    ReadFile(fin, v, N*sizeof(int), &size_read, NULL);
    CloseHandle(fin);
}

void solve()
{
    HANDLE fin = CreateFile ( TEXT ( "input.dat" ), GENERIC_READ, 0, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL );
    
    if ( fin == INVALID_HANDLE_VALUE ) {
        fprintf ( stderr, "ERROR: File %s could not be opened\n", "input.dat" );
        exit ( 1 );
    }
    DWORD size_read;    
    for (int i = 0; i < N; i++)
    {
        ReadFile(fin, a, N*sizeof(int), &size_read, NULL);
        for (int j = 0; j < N; j++)
            ans[i] += (a[j] * v[j]);
    }
    CloseHandle(fin);
}

void out()
{
    HANDLE fout = CreateFile ( TEXT ( "output.dat" ), GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL );
    
    if ( fout == INVALID_HANDLE_VALUE ) {
        fprintf ( stderr, "ERROR: File %s could not be opened\n", "output.dat" );
        exit ( 1 );
    }
    DWORD dwBytesWritten;
    WriteFile(fout, ans, N*sizeof(int), &dwBytesWritten, NULL );
    CloseHandle(fout);
}

int main()
{
    init();
    solve();
    out();
    return 0;
}

Комментарии к коду:
предполагаю что матрица не разрежена, формат хранения данных бинарный, компилировалось и проверялось под WinXP, VS2008. Время выполнения = время на чтение данных с диска, процессор практически простаивал. На тестовой машинке эти 40Гб (N*N*sizeof(int)) обработались (хы, "прочитались") за 30 минут.
P.S. По прикидкам, необходимо памяти 3*N*sizeof(int) ~ 1,2Mb, хотя замеряющая прога по факту намеряла 7,8Mb (сей факт объяснить не могу)

Это сообщение отредактировал(а) Silent - 27.7.2011, 11:53

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »