Come viene algebra lineare utilizzato in algoritmi?

Question

Molti dei miei colleghi hanno detto che "l'algebra lineare" è molto importante quando si studia algoritmi. Ho studiato una varietà di algoritmi e preso alcuni corsi di algebra lineare e non vedo la connessione. Così come è algebra lineare utilizzato in algoritmi?

Per esempio ciò che le cose interessanti può uno con una matrice di connettività per un grafico?

Answer 1

Tre esempi concreti:

• L'algebra lineare è il fondamento della moderna grafica 3D. Questo è essenzialmente la stessa cosa che hai imparato a scuola. I dati sono conservati in uno spazio 3D che si proietta in una superficie 2d, che è quello che si vede sullo schermo.
• La maggior parte dei motori di ricerca si basano su algebra lineare. L'idea è di rappresentare ogni documento come un vettore in uno spazio iper e vedere come il vettore si riferisce a vicenda in questo spazio. Questo è utilizzato dal Lucene , tra gli altri. Vedere VSM .
• Alcuni algoritmi di compressione moderni come quello usato dal formato ogg vorbis si basa su algebra lineare, o più specificamente un metodo chiamato quantizzazione vettoriale .

In sostanza si tratta di fatto che l'algebra lineare è un metodo molto potente quando si tratta di più variabili, e c'è enormi vantaggi per l'utilizzo questo come una base teorica durante la progettazione di algoritmi. In molti casi questa fondazione non è così appearent come si potrebbe pensare, ma questo non significa che non c'è. E 'molto probabile che hai già implementato algoritmi che sarebbe stato incredibilmente difficile da ricavare, senza linalg.

Answer 2

Un crittografo probabilmente vi dirà che una comprensione della teoria dei numeri è molto importante quando si studia algoritmi. E avrebbe ragione - per il suo specifico campo. Statistiche ha i suoi usi troppo -. Skip list, tabelle hash, ecc L'utilità della teoria dei grafi è ancora più evidente

Non c'è alcun legame intrinseco tra l'algebra lineare e algoritmi; c'è un legame intrinseco tra la Matematica e algoritmi.

L'algebra lineare è un campo con molte applicazioni, e gli algoritmi che disegnano su di esso hanno quindi molte applicazioni. Non hai sprecato il vostro tempo a studiarlo.

Answer 3

Ah, non riesco a resistere mettere questo qui (anche se le altre risposte sono buone):

$ 25 miliardi di dollari autovettore .

Non ho intenzione di mentire ... Non ho mai letto il tutto ... forse lo farò ora: -).

Answer 4

Non so se mi piacerebbe frase come 'l'algebra lineare è molto importante quando si studia algoritmi". Mi ero quasi messo il contrario. Molti problemi, molti, molti, del mondo reale finiscono che richiede per risolvere una serie di equazioni lineari. Se si finisce per dover affrontare uno di quei problemi che si sta per bisogno di conoscere alcuni dei tanti algoritmi per trattare con equazioni lineari. molti di questi algoritmi sono stati sviluppati in cui i computer era un titolo di lavoro , non una macchina. Prendere in considerazione l'eliminazione gaussiana ei vari algoritmi di matrice di decomposizione, per esempio. C'è un molto della teoria molto sofisticata su come risolvere questi problemi molto grandi matrici per esempio.

metodi piu 'comuni in apprendimento automatico finiscono per avere una fase di ottimizzazione che richiede la soluzione di un insieme di equazioni simultanee. Se non si conosce l'algebra lineare sarai completamente perso.

Answer 5

Molti algoritmi di elaborazione dei segnali sono basate su operazioni di matrice, ad esempio Trasformata di Fourier, trasformata di Laplace, ...

Problemi di ottimizzazione possono spesso essere ridotti a risolvere sistemi di equazioni lineari.

Answer 6

L'algebra lineare è importante anche in molti algoritmi di computer algebra, come si può immaginare. Ad esempio, se è possibile ridurre un problema a dire che un polinomio è zero, dove i coefficienti del polinomio sono lineari nelle variabili x1, …, xn, allora è possibile risolvere per quali valori di x1, …, xn rendono il pari polinomio a 0 uguagliando il coefficiente di ogni termine x^n a 0 e risolvendo il sistema lineare. Questo è chiamato il metodo dei coefficienti indeterminati, e viene utilizzato ad esempio nel calcolo decomposizioni frazioni parziali o integrare funzioni razionali.

Per la teoria dei grafi, la cosa più bella di una matrice di adiacenza è che se si prende all'ennesima potenza di una matrice di adiacenza di un grafo non ponderata (ogni voce è 0 o 1), M^n, quindi ogni voce i,j sarà il numero di percorsi dal vertice i a vertice j di lunghezza n. E se questo non è solo freddo, quindi non so che cosa è.

Answer 7

Tutte le risposte qui sono buoni esempi di algebra lineare in algoritmi.

Come risposta meta, vorrei aggiungere che si potrebbero utilizzare l'algebra lineare in algoritmi senza saperlo. I compilatori che ottimizzano con SSE (2) tipicamente vectorize il codice da avere molti valori dei dati manipolati in parallelo. Questo è essenzialmente elementare LA.

Answer 8

Dipende che tipo di "algoritmi".

Alcuni esempi:

• Machine-Learning / Statistiche algoritmi: Lineare regressioni (minimi quadrati, cresta, lazo)
.
• compressione con perdita di segnali e di altre lavorazioni (riconoscimento facciale, ecc). Vedere Eigenfaces

Answer 9

  

Per esempio ciò che le cose interessanti può uno con una matrice di connettività per un grafico?

Un sacco di proprietà algebriche della matrice sono invarianti per permutazioni di vertici (ad esempio abs (determinante)), quindi se due grafici sono isomorfi, i loro valori saranno uguali.

Questa è una fonte per buone euristiche per determinare se due grafici sono non isomorfica, dal momento che, naturalmente, l'uguaglianza non garantisce esistenza di isomorfismo.

grafico algebrica teoria per un sacco di altre tecniche interessanti.