Форум программистов, компьютерный форум 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
30.01.2013, 08:38     Оптимизация алгоритма вычисления определителя матрицы #21
-=ЮрА=-, я с вами согласен в чем то) Что да,зависит от исходных данных. Но не зря же дают оценку сверху. И вы понимаете что n! куда хуже n^3.
Ну и вы, раз начали говорить об быстроте алгоритмов-дайте тогда пожалуйста для обоих оценку снизу и среднюю оценку. И желательно док-во,или ссылку на источник.
Я лично находил такие данные(только оценка сверху)
метода Гаусса-O(n3)
разложение Лапласа по определителям меньшего порядка-О(n!)
Штрасена-Винограда - O(n2.81)
Копперсмита — Винограда - O(n2.37)
Прошу Вас)

Добавлено через 14 минут
Исходя из этих цифр я и говорю что лучше а что хуже. Хотелось бы узнать на чем основываетесь вы
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-=ЮрА=-
Заблокирован
Автор FAQ
30.01.2013, 11:21     Оптимизация алгоритма вычисления определителя матрицы #22
"Дорогой", если заплатишь я тебе и анимацию нарисую из фреймов. Давать должен не я а ты!
И хватит тыкать формулы из Вики!Ты хоть бы одну сам вывел либо в ходе рассчётов просуммировал число итераций))
Ещё раз - специализированные матричные методы для разрежённых СЛАУ имеют сложность близкую к O(2*n) (в вики тебе такое точно не напишут)

Цитата Сообщение от Smetanka Посмотреть сообщение
Исходя из этих цифр я и говорю что лучше а что хуже. Хотелось бы узнать на чем основываетесь вы
- на практике работы в облэнерго и работе со специализированными тренажёрами (верней програмной начинки для рассчёта КЗ) - это лучше любой теории

вопрос стоял в другом, кто то не разобравшись и не понимая до конца всех особеннотей СЛАУ(в конкретном случае разрежённость) взял да ляпнул

Цитата Сообщение от Smetanka Посмотреть сообщение
Lexp, считая определитель как говорится "в лоб", или раскладывая по строкам - ты получишь одну и ту же сложность - O(n!) представь что есть сложность О(n)Так что используй метод Гауса. Быстрее ну точно не придумаешь.
-
представь себе что Гаусс часто портит великолепную почти занулённую матрицу увеличивая сроки подсчёта в катастрофически неприемлимой мере!

Итог в результате автор темы если ему не подсказать, что не всегда Гаусс максимально быстр так и будет считать что Гаусс лучше во всех эпостасиях. Вот против этого я и написал свой пост 16.

Не по теме:

Подчеркну я не собираюсь спорить с "зелёными" и частично "зеленоватыми" студентами, которым только что прочли матметоды и они уверовали что знают всё. Лично сам знаю о численных методах довольно много чтобы и это позволяет мне написать - Гаусс в ряде условий только хуже и дольше!



Добавлено через 3 минуты
Кликните здесь для просмотра всего текста
Более писать тут не хочу до момента пока не увижу кодов мыслей рассчётов, моё время слишком дорого чтобы тратить его не втолмачивание истины людям с малым багажом знаний...
Smetanka
56 / 17 / 1
Регистрация: 14.05.2012
Сообщений: 134
30.01.2013, 11:49     Оптимизация алгоритма вычисления определителя матрицы #23
-=ЮрА=-, я и не говорю со мной спорить! Я говорю-дайте мне факты, или место,откуда их черпать. Вы думаете что человек должен до всего доходить сам? Тогда не будет прогресса,все мы будем топтаться на месте. Я уверен что Ваш опыт куда более весомее моего. Дак поделитесь же им! Сколько времени у Вас ушло,чтобы понять какой метод лучше? Уйма! Почему бы не помочь "зеленому студенту" и не рассказать по подробнее что лучше,а что хуже. В самом деле-я считаю что для этого и сделан форум,чтобы делится ОПЫТОМ. А если Вам некогда, то тогда зачем говорить "А", но потом не говорить "Б"?

Не по теме:

И я основывался не только на википедии.

silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
31.01.2013, 08:24     Оптимизация алгоритма вычисления определителя матрицы #24
-=ЮрА=-, зачем вы насели на разрежённые матрицы? Алгоритмы на разрежённых матрицах - вообще отдельная тема, не имеющая ничего общего с общим случаем (прошу прощения за каламбур). Разрежённые матрицы просто так, случайно, не встречаются. Обычно заранее известно, что они будут использоваться при решении задачи. И тут уж надо подходить совсем с другой стороны, использовать специализированные методы, начиная от самого представления их в памяти. В общем же случае, когда имеется матрица, просто матрица и всё тут, я бы всё же воспользовался Гауссом, или, если известно, что фигурируют только очень большие матрицы, более быстрыми методами (о которых уже писалось выше).
-=ЮрА=-
Заблокирован
Автор FAQ
31.01.2013, 13:21     Оптимизация алгоритма вычисления определителя матрицы #25
silent_1991 я налёг по причинам которые изложены выше в посте 22 и ещё на пару постов до этого и считаю что правильно сделал.
Повторюсь :
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
вопрос стоял в другом, кто то не разобравшись и не понимая до конца всех особеннотей СЛАУ(в конкретном случае разрежённость) взял да ляпнул
Сообщение от Smetanka
Lexp, считая определитель как говорится "в лоб", или раскладывая по строкам - ты получишь одну и ту же сложность - O(n!) представь что есть сложность О(n)Так что используй метод Гауса. Быстрее ну точно не придумаешь.
-
представь себе что Гаусс часто портит великолепную почти занулённую матрицу увеличивая сроки подсчёта в катастрофически неприемлимой мере!
- суть сводилась к тому что Гаусс далеко не самый быстрый и матричное решение иногда может дать фору даже самым продуманным быстрым методам(хотя большинство из них тот же матричный но с изощрениями). Предлагаю закрыть тему, коды есть слова есть

Не по теме:

Для Smetanka

Кликните здесь для просмотра всего текста
Цитата Сообщение от Smetanka Посмотреть сообщение
Я уверен что Ваш опыт куда более весомее моего. Дак поделитесь же им! Сколько времени у Вас ушло,чтобы понять какой метод лучше? Уйма! Почему бы не помочь "зеленому студенту" и не рассказать по подробнее что лучше,а что хуже.
- с 8 до 17-ти на работе, возвращаюсь домой плачет 2 х месячный ребёнок, соц помощь пока не дали и я вынужден бомбить днями и ночами, чтобы банально обеспечить семью!Не могу Я в данный период жизни тратить время на разъяснения и прочее. Если нужны пояснения - деньги на бочку, нет - идём в мой FAQ на который дал 2 линка в этой теме и копипастя код сравниваем отработки на СЛАУ различного размера. Мне пока не до теревенй, мне жить надо

mamrenko_
0 / 0 / 0
Регистрация: 24.04.2014
Сообщений: 1
30.05.2014, 12:25     Оптимизация алгоритма вычисления определителя матрицы #26
-=ЮрА=-, можешь перевести код на с++? очень надо до понедельника. Спасибо большое
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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
 
//Функция находит минор матрицы arr для элемента
//с индексами строки im столбца jm
double **M(int m, int im, int jm, double ** arr)
{
    int i, j;
    printf("Minor : m = %02d im = %02d, jm = %02d\n", m, im, jm);
    double ** ret = (double **)malloc((m - 1)*sizeof(double));
    for(i = 0; i < m; i++)
    {
        if(i != im)
        {
            if(i < im)
                ret[i]     = (double *)malloc((m - 1)*sizeof(double));
            else
                ret[i - 1] = (double *)malloc((m - 1)*sizeof(double));
            for(j = 0; j < m; j++)
            {
                if(j != jm)
                {
                    if(i < im)
                    {
                        if(j < jm)
                            printf("%.0f ",(ret[i][j] = arr[i][j]));
                        else
                            printf("%.0f ",(ret[i][j - 1] = arr[i][j]));
                    }
                    else
                    {
                        if(j < jm)
                            printf("%.0f ",(ret[i - 1][j] = arr[i][j]));
                        else
                            printf("%.0f ",(ret[i - 1][j - 1] = arr[i][j]));
                    }
                }
            }
            printf("\n");
        }
    }
    return ret;
}
 
//Функция возвращает детерминант матрицы
//В функции всё понятно кроме 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;
}
 
int main()
{
    int i, j, m;
    //По умолчанию ставлю светить результаты
    int iShowStepsOfCalcs = 1;//промежуточных вычислений
    printf("Enter m : ");scanf("%d",&m);
    time_t t;srand(time(&t));
    //Выделяем память под строки массива
    double ** array = (double **)malloc(m*sizeof(double));
    double det = 0;//Будет содержать в себе результат вычислений
    for(i = 0; i < m; i++)
    {
        //Выделяем память под элементы строки
        array[i] = (double *)malloc(m*sizeof(double));
        for(j = 0; j < m; j++)
        {
            //Будут как отр так и положит элементы
            array[i][j] = (1.0*(rand()%100) - 50)/10;
            //Я немного модернизировал вывод чтобы
            //отрицательные и положительные печатались ровно
            printf
            (
                (array[i][j] < 0 ? "-%.1f " : " %.1f "),
                fabs(array[i][j])
            );
        }
        printf("\n");
    }
    system("pause");
    det = Det(m,array,iShowStepsOfCalcs);
    system("cls");//Очищаем экран
    //Заново печатаем элементы матрицы(можно и не делать, 
    //повторный вывод ввёл просто для удобства пользования
    //Ну и заодно чистим память
    for(i = 0; i < m; i++)
    {
        for(j = 0; j < m; j++)
        {
            printf
                (
                    (array[i][j] < 0 ? "-%.1f " : " %.1f "),
                    fabs(array[i][j])
                );
        }
        printf("\n");
        free((void *)array[i]);
    }
    printf("Determiant : %lf\n",det);
    system("pause");
    return 0;
}
Kerry_Jr
Модератор
 Аватар для Kerry_Jr
1866 / 1662 / 579
Регистрация: 14.05.2014
Сообщений: 4,772
Записей в блоге: 1
Завершенные тесты: 5
31.05.2014, 17:37     Оптимизация алгоритма вычисления определителя матрицы #27
Укажите глупцу на ошибки, если не сложно
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
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <ctime>
 
double**  Minor(double** matrix, int size, int i, int j)
{
    double** minor = new double*[size-1];
    for (int k = 0; k < size-1; k++)
        minor[k] = new double[size-1];
    for (int x = 0; x < size; x++)
        for (int y = 0; y < size; y++)
            {
                if (x < i && y < j)
                    minor[x][y] = matrix[x][y];
                else if (x > i && y > j)
                    minor[x-1][y-1] = matrix[x][y];
                else if (x > i)
                    minor[x-1][y] = matrix[x][y];
                else if (y > j)
                    minor[x][y-1] = matrix[x][y];
            }
    return minor;
}
 
double Determinant(double** matrix, int size)
{
    if (size == 1)
        return matrix[0][0];
    else if  (size == 2)
        return matrix[0][0]*matrix[1][1] - matrix[0][1]*matrix[1][0];
    double determinant = 0;
    for (int j = 0; j < size; j++)
    {
        if(!matrix[0][j]) continue;
        double** minor = Minor(matrix,size-1, 0, j);
        determinant += pow(-1.f,(j+1))*matrix[0][j]*Determinant(minor, size);
        for (int k = 0; k < size-1; k++)
        {
            delete[] minor[k];
            minor[k] = 0;
        }
        delete[] minor;
    }
    
    return determinant;
}
 
int main()
{
    setlocale(LC_ALL, "");
    srand(unsigned(time(NULL)));
    int size;
    std::cout << "Введите размер массива: ";
    std::cin >> size;
    double** arr = new double*[size];
    for (int i = 0; i < size; i++)
        arr[i] = new double[size];
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            arr[i][j] = rand() % 10;
            std::cout << arr[i][j] << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
    std::cout << "Определитель матрицы: " << Determinant(arr, size) << std::endl;
    for (int i = 0; i < size; i++)
    {
        delete[] arr[i];
        arr[i] = 0;
    }
    delete[] arr;
    
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.05.2014, 17:48     Оптимизация алгоритма вычисления определителя матрицы
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Lexp
3 / 3 / 1
Регистрация: 02.07.2012
Сообщений: 45
31.05.2014, 17:48  [ТС]     Оптимизация алгоритма вычисления определителя матрицы #28
Kerry_Jr, если не считать некоторой неаккуратности кода, то смею предположить, что дело в:
C++
1
determinant += pow(-1.f,(j+1))*matrix[0][j]*Determinant(minor, size);
pow(-1.f, (j+1)) следует заменить на pow(-1.f, j).
И вообще, код в первом сообщении этой темы - рабочий, сверься с ним.
Yandex
Объявления
31.05.2014, 17:48     Оптимизация алгоритма вычисления определителя матрицы
Ответ Создать тему
Опции темы

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