Newsgroup: it.scienza.informatica
Titolo: Calcolo del determinante

Ho provato per esercizio a scrivere un programma che sia in grado di
calcolare il determinante di una matrice quadrata di qualsiasi ordine. Per
farlo ho utilizzato l'algoritmo di Laplace, cioč il determinante č pari alla
somma dei prodotti degli elementi di una riga per il complemento algebrico
dell'elemento stesso. Cosě ad esempio il det.della matrice
       | 1  3  2|
       | 0  2  3|  =  1* | 2  3 | - 3 * | 0  3 |  +  2 * | 0  2 | =  1 * ( 2
* | 1 | - 3 * | 1 |) -.....=
       | 2  1  1|           | 1  1 |          | 2  1 |            | 2  1 |
                     =  1 *(-1)  -  3 *(-6)  +  2 *(-4) = 9
Si tratta di un algoritmo ricorsivo in cui la condizione di stop si verifica
quando si ha una matrice del primo ordine.
Il problema č che, fissato come punto di riferimento il tempo per calcolare
una matrice 2 x 2, il calcolo di una 3x3 impiega circa 3 volte tanto, quello
di una 4x4 12 volte. In generale una n x n dovrebbe impiegare n! / 2 volte
una 2 x 2. Poichč una 10x10 sul mio PC impiega circa 35 secondi, una 20 x 20
dovrebbe restituire il risultato ai nostri discendenti visto che impiega piů
di 700.000 anni!
Non che mi serva attualmente fare calcoli di questo tipo, mi chiedevo
tuttavia se esistesse un altro algoritmo(magari non ricorsivo) che permetta
di velocizzare un po' i tempi.
Volendo invece mantenere questo algoritmo, cosa potrei cambiare nel mio
codice per aumentare le prestazioni? Io ho pensato che potrebbe essere utile
cercare la riga o la colonna che contiene il numero maggiore di zeri,
evitando in tal modo il calcolo, solo perň se ci sono degli zeri!
Spero di non avervi annoiato con queste mie curiositŕ.
Marco
#include <iostream>
#include <stdlib.h>
#include <iomanip>
#include <time.h>
typedef int Type;
class Matrix
{
friend ostream& operator<<(ostream&, const Matrix&);
friend int det(const Matrix&);
public:
     Matrix();
     Matrix(int, int);
     ~Matrix();
     Matrix(const Matrix&);
     void set(Type,int, int);
     void set_random();
     Matrix minore(int i,int j) const;
private:
     Type** m;
     int rows;
     int cols;
};
Matrix::Matrix() {
     m = 0;
     rows = 0;
     cols = 0;
}
Matrix::Matrix(int righe, int colonne) {
     rows = righe;
     cols = colonne;
     if(!(rows && cols)) {
          m = 0;
          return;
     }
     m = new Type*[rows];
     for(int i = 0; i < rows; i++)
          m[i] = new Type[cols];
     for(int i = 0; i < rows; i++)
          for(int j = 0; j < cols; j++)
               m[i][j] = 0;
}
Matrix::Matrix(const Matrix& M) {
     rows = M.rows;
     cols = M.cols;
     m = new Type*[rows];
     for(int i = 0; i < rows; i++)
          m[i] = new Type[cols];
     for(int i = 0; i < rows; i++)
          for(int j = 0;j < cols; j++)
               m[i][j] = M.m[i][j];
}
Matrix::~Matrix() {
     for(int i = 0; i < rows; i++)
          delete[] m[i];
     delete[] m;
}
void Matrix::set(Type elem, int i, int j) {
     if(i < 0 || i >= rows) {
          cout << "(" << i << "," << j << ")" << " out of range" << endl;
      return;
     }
     if(j < 0 || j >= cols) {
          cout << "(" << i << "," << j << ")" << " out of range" << endl;
      return;
     }
     m[i][j] = elem;
}
void Matrix::set_random() {
        srand(time(0));
     for(int i = 0; i < rows; i++)
          for(int j = 0; j < cols; j++)
               m[i][j] = rand()%4;
}
Matrix Matrix::minore(int noi, int noj) const{
     Matrix result(rows - 1, cols - 1);
     for(int si = 0, di = 0; si < rows; si++)
     {
          for(int sj = 0, dj = 0; sj < cols; sj++)
          {
           if((si != noi) && (sj != noj))
                result.set(m[si][sj], di, dj);
           if(sj != noj) dj++;
          }
          if(si != noi) di++;
     }
     return result;
}
ostream& operator<<(ostream& os, const Matrix& M) {
     for(int i = 0; i < M.rows; i++) {
          for(int j = 0; j < M.cols; j++)
               os << setw(3) << M.m[i][j];
      os << endl;
     }
     return os;
}
// ************************************************
int det(const Matrix& M) {
       int result = 0;
        if(M.rows != M.cols) {
          cout << "Solo matrici quadrate" << endl;
          return 0;
         }
         if(M.cols == 1)
              return M.m[0][0]; // Condizione di stop
         for(int j = 0; j < M.cols; j++) {
               if(j%2)  // colonna dispari
                   result -= M.m[0][j] * det(M.minore[0][j]);
              else if(!(j%2)) // colonna pari
                   result += M.m[0][j] * det(M.minore[0][j]);
         }
            return result;
}
// ************************************************
int main() {
    for(int i = 0; i < 25; i++)
 cout << "\n";
    int dim;
    cout << "Dimensione? ";
                cin >> dim;
    Matrix A(dim, dim);
 A.set_random();
//    cout << A << endl;
 cout << det(A) << endl;
 return 0;
}

L'utilizzo della formula di Laplace per il calcolo del determinante comporta
l'effettuazione di almeno n! moltiplicazioni. Se usi, per esempio la
fattorizzazione di Gauss (data una matrice quadrata A si possono trovare L e
U entrambe triangolari con U avente sulla diagonale gli autovalori di A, da
cui puoi calcolare il determinante), puoi risolvere il problema in tempo
O(n^3).
Per ulteriori chiarimenti:
Ugo Dal Lago
udal...@acm.org