Форум программистов, компьютерный форум CyberForum.ru

Оптимизация алгоритма вычисления определителя матрицы - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 67, средняя оценка - 4.99
Lexp
3 / 3 / 1
Регистрация: 02.07.2012
Сообщений: 45
29.01.2013, 15:39     Оптимизация алгоритма вычисления определителя матрицы #1
Здравствуйте!
Написал я давеча программку, которая считает определитель. Только вот беда - он не считает определители матриц выше 10 порядка - тупо не хватает памяти. Я так понимаю, это из-за того, что мой алгоритм - рекурсивный. Так вот, можно ли больше оптимизировать мой код, или эта рекурсия - заведомо плохой вариант?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
//Определитель вычисляется по формуле det( A ) = a( i, j ) * ( -1 )^( i + j ) * M( i, j ) ( a^b - "а" в степени "b" )
//Минор ищется рекурсивно до тех пор, пока его порядок не стал равен 2 ( тогда в силу вступает формула a( 1, 1 ) * a( 2, 2 ) - a( 1, 2 ) * a( 2, 1 ) )
//На каждом шаге определитель находится путем разложения по наиболее "оптимизированной" строке ( в которой больше всего нулей ) данной на вход матрицы
 
//Примечание: в этих комментариях считается, что коэф. пробегают значения от 1 до n ( в самой программе они пробегают значения от 0 до n-1 )
 
#include <time.h>
#include <iostream>
#include <math.h>
 
using namespace std;
 
//Функция нахождения у матрицы порядка size минора M( str, stb ) ( возвращает минор в матричном представлении )
int **FIND_Minor( int **matrix, int size, int str, int stb )
{
    int **minor = new int *[ size - 1 ];
    
    //m_str, m_stb - коэффициенты, с помощью которых строится сам минор
    int m_str = 0;
    int m_stb;
    for( int i = 0; i < size; i++ )
    {
        //Элементы из строки с номером str не записываются в минор
        if( i != str )
        {
            m_stb = 0;
            minor[ m_str ] = new int[ size - 1 ];
            for( int j = 0; j < size; j++ )
            {
                //Элементы из столбца с номером stb не записываются в минор
                if( j != stb )
                {
                    minor[ m_str ][ m_stb ] = matrix[ i ][ j ];
                    m_stb++;
                }
            }
            m_str++;
        }
    }
 
    return minor;
}
 
int FIND_Det( int **matrix, int size )
{
    //Проверка условия выхода из рекурсии
    if( size == 2 )
    {
        return matrix[ 0 ][ 0 ] * matrix[ 1 ][ 1 ] - matrix[ 0 ][ 1 ] * matrix[ 1 ][ 0 ];
    }
    else if( size == 1 )
    {
        return matrix[ 0 ][ 0 ];
    }
 
    //Момент оптимизации - ищем строку, в которой больше всего нулей, чтобы по ней находить определитель
    //Работает в связи с условием разложения по строке, которое пояснено ниже
    int max_0, str_0 = 0, max_0_b = 0;
    for( int i = 0; i < size; i++ )
    {
        max_0 = 0;
        for( int j = 0; j < size; j++ )
        {
            if( matrix[ i ][ j ] == 0 )
            {
                max_0++;
            }
        }
        if( max_0 > max_0_b )
        {
            str_0 = i;
            max_0_b = max_0;
        }
    }
 
    //Само рекурсивное разложение по строке
    int result = 0;
    for( int j = 0; j < size; j++ )
    {
        //Небольшой момент оптимизации - если текущий элемент в строке равен нулю, то дальше продолжать рекурсию нету смысла 
        //( т.к. произведение будет равно нулю в любом случае )
        if( matrix[ str_0 ][ j ] )
        {
            result += matrix[ str_0 ][ j ] * ( unsigned )pow( -1.f, ( unsigned )j ) * FIND_Det( FIND_Minor( matrix, size, str_0, j ), size - 1 );
        }
    }
 
    return result;
}
 
int main()
{
    srand( ( unsigned )time( NULL ) );
 
    float begin, end;
 
    int size;
    cout << "Enter size: ";
    cin >> size;
    int **matrix = new int*[ size ];
 
    char sw;
    cout << "\n1 - Typing automatically\n2 - Typing manually\n";
    cin >> sw;
 
    switch( sw )
    {
    case '1':
        cout << "\nMatrix:\n";
        for( int i = 0; i < size; i++ )
        {
            matrix[ i ] = new int[ size ];
            for( int j = 0; j < size; j++ )
            {
                matrix[ i ][ j ] = rand()%10;
                cout << matrix[ i ][ j ] << " ";
            }
            cout << "\n";
        }
        break;
 
    case '2':
        cout << "\nYour matrix:\n";
        for( int i = 0; i < size; i++ )
        {
            matrix[ i ] = new int[ size ];
            for( int j = 0; j < size; j++ )
            {
                cin >> matrix[ i ][ j ];
            }
        }
        break;
 
    default:
        cout << "\n";
        system( "pause" );
        return 0;
    }
 
    cout << "\nDeterminant = ";
    begin = clock();
    cout << FIND_Det( matrix, size ) << endl;
    end = clock();
 
    cout << "\nTask time - ";
    cout << ( end - begin ) / 1000 << " seconds" << endl;
 
    system( "pause" );
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.01.2013, 15:39     Оптимизация алгоритма вычисления определителя матрицы
Посмотрите здесь:

C++ Улучшение алгоритма вычисления определителя матрицы, порядка n>3
Подстроение алгоритма определителя C++
Оптимизация алгоритма C++
Оптимизация алгоритма C++
Код вычисления определителя матрицы до 10-го порядка C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Smetanka
56 / 17 / 1
Регистрация: 14.05.2012
Сообщений: 134
29.01.2013, 17:16     Оптимизация алгоритма вычисления определителя матрицы #2
Lexp, ну сама по себе рекурсия есть не очень хорошо в плане скорости. Странно что не хватает памяти(а как вы поняли что ее не хватает?) ведь у компьютера сейчас например 2гб оперативной памяти + подкачка. Короче много. Плюс ко всему сам по себе ваш алгоритм поиск миноров( разложение Лапласа кажется правильно ) ну ооочень медленный. Работает аж за O(n!). Например у вас 10!=3628800. Может и можно как то оптимизировать,если хорошо проанализировать код(убрать какие нибудь ненужные действия,или как нибудь их объединить),но высокого прироста к производительности вы не получите
-=ЮрА=-
Заблокирован
Автор FAQ
29.01.2013, 17:30     Оптимизация алгоритма вычисления определителя матрицы #3
Lexp, посмотри 4.4.3 Матричный способ нахождения определителя
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
29.01.2013, 18:16     Оптимизация алгоритма вычисления определителя матрицы #4
У вашего алгоритма страшная сложность. Горадо лучше привести эту матрицу к треугольному виду гауссом, а там уже несложно посчитать детерминант за линию.
Lexp
3 / 3 / 1
Регистрация: 02.07.2012
Сообщений: 45
29.01.2013, 18:24  [ТС]     Оптимизация алгоритма вычисления определителя матрицы #5
Цитата Сообщение от diagon Посмотреть сообщение
У вашего алгоритма страшная сложность. Гораздо лучше привести эту матрицу к треугольному виду гауссом, а там уже несложно посчитать детерминант за линию.
Да, сложность кошмарная, тут согласен. Видимо придется действительно Гаусса использовать, как-то сразу не додумался...
-=ЮрА=-
29.01.2013, 18:34
  #6

Не по теме:

Цитата Сообщение от Lexp Посмотреть сообщение
Да, сложность кошмарная, тут согласен. Видимо придется действительно Гаусса использовать, как-то сразу не додумался...
- ели считать по свойству определителя то Гассу нет! Гаусс может лишь рассматриваться как оптимизация да и то не из лучших, те кто пишут им определители просто идут по пути наименьшего сопротивления. Причём всегда надо пробовать идти по нелёгкому пути, чтобы потом сравнить с лёгким и выбрать лучшее для той или иной СЛАУ.

Lexp
3 / 3 / 1
Регистрация: 02.07.2012
Сообщений: 45
29.01.2013, 18:40  [ТС]     Оптимизация алгоритма вычисления определителя матрицы #7
Самый нелегкий путь тут - нахождение определителя прямо по определению (сумма всевозможных комбинаций того-то и того-то). Там и сложность по идее меньше будет, только вот как реализовать...
-=ЮрА=-
Заблокирован
Автор FAQ
29.01.2013, 18:50     Оптимизация алгоритма вычисления определителя матрицы #8
Цитата Сообщение от Lexp Посмотреть сообщение
амый нелегкий путь тут - нахождение определителя прямо по определению (сумма всевозможных комбинаций того-то и того-то). Там и сложность по идее меньше будет, только вот как реализовать...
- ну так по линку в посте выше так его и нахожу

Не по теме:

Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
При этом, с помощью миноров можно облегчать задачу вычисления определителя матрицы. Надо разложить определитель матрицы по некоторой строке и тогда определитель будет равен сумме всех элементов этой строки на их миноры. Разложение определителя матрицы 3 - его порядка будет выглядеть так:
знак перед произведением равен aij и Mij



Добавлено через 1 минуту
Причем ниже в 5.2 уже вообще сингл функция детерминанта идёт
Кликните здесь для просмотра всего текста
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//Функция возвращает детерминант матрицы
//В функции всё понятно кроме iShowStepsOfCalcs 
//iShowStepsOfCalcs - это флаг отвечающий за то чтобы
//светить или нет в консоли результаты промежуточных вычислений
//Вообще вывод промежуточных вычислений полезнаяя штука для понимания
//работы рекурсии, кому понтравится может перенаправить вывод
//промежуточных результатов в файл. Единственный минус промежуточной индика
//ции - существенное увелечиние времени вычислений
double Det(int m, double ** arr, int iShowStepsOfCalcs)
{
    int i, j = 0;
    double ret = 0;
    double A;
    double ** _arr;
    if(m == 2)//В случаем 2х2 вычисляем детерминант сразу
    {
        ret = 
            arr[0][0]*arr[1][1] - 
            arr[1][0]*arr[0][1];
        if(iShowStepsOfCalcs)
            printf("Det = %lf\n",ret);
        
    }
    else//Иначе находим детерминант рекурсивно
    //через алгебраическое дополнение элемента
    {
        for(j = 0; j < m; j++)
        {
            _arr = M(m, 0, j, arr);
            ret += (A = (arr[0][j])*pow(-1,j)*Det(m - 1, _arr, iShowStepsOfCalcs));
            if(iShowStepsOfCalcs)
                printf("A[%02d][%02d] = %lf\n",1, j + 1,A);
            for(i = m - 2; 0 < i; i--)
                free((void *)_arr[i]);
            free((void *)_arr);
        }
    }
    return ret;
}
Lexp
3 / 3 / 1
Регистрация: 02.07.2012
Сообщений: 45
29.01.2013, 19:06  [ТС]     Оптимизация алгоритма вычисления определителя матрицы #9
Не-не-не, я имею в виду не рекурсивное разложение по строке, а именно сумма всех комбинаций элементов, взятых по одному из каждого столбца и каждой строки.
Smetanka
56 / 17 / 1
Регистрация: 14.05.2012
Сообщений: 134
29.01.2013, 19:25     Оптимизация алгоритма вычисления определителя матрицы #10
Lexp, считая определитель как говорится "в лоб", или раскладывая по строкам - ты получишь одну и ту же сложность - O(n!)
Метод Гауса дает более лучший результат - O(n3)
Так что используй метод Гауса. Быстрее ну точно не придумаешь.
p.s. Есть алгоритмы,которые работают быстрее, но они быстрее лишь на ОООООЧЕЕЕНЬ больших матрицах
Kgfq
74 / 37 / 2
Регистрация: 23.09.2012
Сообщений: 408
29.01.2013, 19:30     Оптимизация алгоритма вычисления определителя матрицы #11
Можно программно посчитать какие на какие элементы нужно перемножить (в индексах), что бы получить определитель и сохранить в файлик. А потом из файлика считать и в цикле посчитать. Чем не вариант?
Lexp
3 / 3 / 1
Регистрация: 02.07.2012
Сообщений: 45
29.01.2013, 19:34  [ТС]     Оптимизация алгоритма вычисления определителя матрицы #12
Цитата Сообщение от Smetanka Посмотреть сообщение
Lexp, считая определитель как говорится "в лоб", или раскладывая по строкам - ты получишь одну и ту же сложность - O(n!)
Метод Гауса дает более лучший результат - O(n3)
Так что используй метод Гауса. Быстрее ну точно не придумаешь.
p.s. Есть алгоритмы,которые работают быстрее, но они быстрее лишь на ОООООЧЕЕЕНЬ больших матрицах
Да, я тоже подумал, кол-во слагаемых будет как раз n!
Наверно тупо сделаю Гаусса и сравню с текущим алгоритмом.

Добавлено через 2 минуты
Цитата Сообщение от Kgfq Посмотреть сообщение
Можно программно посчитать какие на какие элементы нужно перемножить (в индексах), что бы получить определитель и сохранить в файлик. А потом из файлика считать и в цикле посчитать. Чем не вариант?
Вот это "программно посчитать" как раз в n! и выйдет...если я правильно вашу идею понял
Kgfq
74 / 37 / 2
Регистрация: 23.09.2012
Сообщений: 408
29.01.2013, 19:36     Оптимизация алгоритма вычисления определителя матрицы #13
Lexp, для матрицы 2x2 это было бы:

00 01
10 11

00 * 11 - 01 * 10
в индексах. Ну или еще можно попробовать упростить матрицу до того, что бы большинство оказалось нулями
Smetanka
56 / 17 / 1
Регистрация: 14.05.2012
Сообщений: 134
29.01.2013, 19:38     Оптимизация алгоритма вычисления определителя матрицы #14
Kgfq, это и есть определение определителя. Математики уже соптимизировали и доказали все что можно) Метод Гауса-самый быстрый и вменяемый метод(вплане алгоритма).
С другой стороны,как вариант, можно распараллелить данную программу-но это уже не оптимизация алгоритма,а оптимизация программы.

Добавлено через 1 минуту
Lexp, Гаусом не тупо, Гаусом правильно) Ты на верном пути! И поверь быстрее ты не придумаешь)))
Lexp
3 / 3 / 1
Регистрация: 02.07.2012
Сообщений: 45
29.01.2013, 19:38  [ТС]     Оптимизация алгоритма вычисления определителя матрицы #15
Цитата Сообщение от Kgfq Посмотреть сообщение
Lexp, для матрицы 2x2 это было бы:

00 01
10 11

00 * 11 - 01 * 10
в индексах. Ну или еще можно попробовать упростить матрицу до того, что бы большинство оказалось нулями
Для матрицы 3х3 уже 6 слагаемых. И т.д.
-=ЮрА=-
Заблокирован
Автор FAQ
29.01.2013, 22:27     Оптимизация алгоритма вычисления определителя матрицы #16
Цитата Сообщение от Smetanka Посмотреть сообщение
Lexp, Гаусом не тупо, Гаусом правильно) Ты на верном пути! И поверь быстрее ты не придумаешь)))
- ты уверен(а) в своих словах, проверька Гасса на разрежённой матрице 4000х4000 порядка, посомтришь что быстрей "матрица" или Гаусс, преращающий в кучу числе почти занулённую матрицу!
А вот всякие шапкозакидатели вроди тебя сбивают люд с пути истинного!
Детерминант в FAQ я дал, ниже там идёт и метод Гаусса.
Аргументируй вот это своё выссказывание
Цитата Сообщение от Smetanka Посмотреть сообщение
Гаусом не тупо, Гаусом правильно) Ты на верном пути! И поверь быстрее ты не придумаешь)))
. А я говрю Гауссом иногда тупее чем определителем, и?!

Не по теме:

PS:Если кто-то не в силах что-то написать - это не значит что это "что-то" глупость либо нерационально ИМХО!

Kgfq
74 / 37 / 2
Регистрация: 23.09.2012
Сообщений: 408
29.01.2013, 22:33     Оптимизация алгоритма вычисления определителя матрицы #17

Не по теме:

-=ЮрА=-, вы так брызгаете слюной, что текст сложно читать. Нельзя ли писать спокойней, рассудительней и главное - понятней.



А по теме, если автор напишет Гауссом, то можно будет сравнить методы, которыми вы пользуетесь
-=ЮрА=-
Заблокирован
Автор FAQ
29.01.2013, 22:36     Оптимизация алгоритма вычисления определителя матрицы #18
А для "Фом неверующих" на словах: если взять матрицу в которой ненулевых элементов кот наплакал, то можно подобрать такую строку в которой 1 элемент и все остальные - нули. И что получаем - найти детерминант на порядок ниже надо, всего один, причем если стопорить расчёт детерминанта как только в сомножителе ноль, то можно получить КОЛОСАЛЬНЕЙШИЙ выиграш в производительности и скорости. А вот Гаусс добросовестно будет
2 х (4000 * 4000) раз ворочать матрицу состоящую скажем из 80% нулей, нет слов эффективно до боли....
Kgfq
74 / 37 / 2
Регистрация: 23.09.2012
Сообщений: 408
29.01.2013, 22:39     Оптимизация алгоритма вычисления определителя матрицы #19
-=ЮрА=-, вы рассматриваете крайности. Это уже вопрос динамического расчета и применения наиболее эффективного в данный момент. Но, т.к. вероятность выпадения 0 в матрице бесконечно мала (по сравнению с R), то метод Гаусса более оптимальный
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.01.2013, 22:46     Оптимизация алгоритма вычисления определителя матрицы
Еще ссылки по теме:

C++ Сделать класс для вычисления определителя
C++ Написать функцию для вычисления определителя матрицы
Создать функцию для вычисления определителя матрицы 2х2 C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
-=ЮрА=-
29.01.2013, 22:46     Оптимизация алгоритма вычисления определителя матрицы
  #20

Не по теме:

Цитата Сообщение от Kgfq Посмотреть сообщение
Но, т.к. вероятность выпадения 0 в матрице бесконечно мала
- дружок поищи матрицу соединения узлов энергосистемы да рассчитай там ток и напряжение в каждом элементе при К(1,1) в оной из ветвей, а потом сравни с матричным способом...Вероятность нуля мала))) ну да в СЛАУ для студентов она и правда мала, а в реалии всё совсем совсем по другому. В реалии во многих сферах рулят крайне разрежённые СЛАУ. На сим не хочу продолжать не нужный мне спор или переубеждение. Я могу, верней я писал и "детерминант по определению" и метод Гаусса и знаю что где применимо и какая у чего производительность в близи краевых условий...

Yandex
Объявления
29.01.2013, 22:46     Оптимизация алгоритма вычисления определителя матрицы
Ответ Создать тему
Опции темы

Текущее время: 08:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru