L’algebra di Clifford e il rasoio di Occam Giorgio Vassallo Silvia Franchini Seminario di Logica e...

L’algebra di Clifford e il rasoio di Occam

Giorgio VassalloSilvia Franchini

Seminario di Logica e Filosofia della Scienza Università degli Studi di Palermo 27/11/2013

Conoscenza e modelli

La conoscenza scientifica si fonda sulla creazione e la validazione di modelli e paradigmi in grado di codificare e interpretare sia concetti astratti che dati sperimentali.

E’ possibile definire formalmente la qualità di un modello/paradigma?

27/11/2013Seminario di Logica e Filosofia della Scienza Università degli Studi di Palermo

Il Rasoio di Occam

Il principio logico del rasoio di Occam afferma il valore della semplicità e della sinteticità.

Tra i diversi modelli che consentono di spiegare un dato fenomeno, si deve preferire il modello più semplice, che non introduce enti inutili.


“Pluralitas non est ponenda sine necessitate”

“Frustra fit per plura quod potest fieri per

pauciora”

“Entia non sunt multiplicanda praeter

necessitatem”

Guglielmo di Occam

“Pluralitas non est ponenda sine necessitate”

“Frustra fit per plura quod potest fieri per

pauciora”

“Entia non sunt multiplicanda praeter

necessitatem”

Guglielmo di Occam

Formalizzazione del rasoio di Occam

La qualità di un modello è definita da:

1.Aderenza ai dati e concetti che si vogliono codificare o interpretare (misura di distanza delle informazioni fornite dal modello rispetto alle informazioni attese, es. dati sperimentali)

2.Complessità (numero di assi concettuali, paradigmi, postulati, parametri, variabili necessari alla costruzione del modello)


Modelli di massima entropia

Principio della Massima Entropia o MaxEnt(E. T. Jaines)

“In presenza di dati e/o evidenze sperimentali riguardanti un ben determinato fenomeno fisico o statistico, per stimarne la relativa distribuzione di probabilità, è sufficiente scegliere un modello che sia [il più possibile] consistente con i dati disponibili ma che altrove abbia la massima entropia.”


I modelli della conoscenza scientifica

La conoscenza scientifica si fonda sul linguaggio matematico.

Dal punto di vista strettamente epistemologico, seguendo il principio del rasoio di Occam, è fondamentale, quindi, utilizzare un linguaggio ottimale in termini di semplicità e universalità.

Ad esempio, il paradigma classico per formalizzare i concetti della geometria e della fisica mette insieme una serie di simbolismi e linguaggi matematici diversi che violano il principio di massima semplicità portando ad una costosa e pesante frammentazione della conoscenza.


Il paradigma classico

Il paradigma tradizionalmente usato per formalizzare i concetti della geometria e della fisica è fondato sull’algebra lineare.

L’algebra lineare classica utilizza un insieme limitato di elementi (scalari e vettori) che sono manipolati attraverso un insieme limitato di operatori (prodotto scalare, definito per tutte le dimensioni, e prodotto vettoriale, definito solo in tre dimensioni).



Le limitazioni dell’algebra lineare hanno portato alla formulazione di tanti micro-modelli separati e alla creazione di una Babele di linguaggi matematici diversi:

Numeri complessi

Quaternioni

Algebra vettoriale

Matrici di Dirac

Coordinate di Plücker

Coordinate omogenee

Spinori

Forme differenziali

Trasformazioni di Lorentz

Equazioni di Maxwell



Gli stessi concetti sono rappresentati in tanti sistemi diversi.

Ciò comporta costi enormi in termini delle necessarie traduzioni per passare da una rappresentazione all’altra.

Tutte le algebre usate per modellare la fisica e la geometria si possono rappresentare come algebre di matrici.

Le matrici nascondono la semantica delle informazioni, per esempio il significato geometrico delle informazioni codificate. Ad esempio, le matrici ortogonali per rappresentare le rotazioni nascondono il piano e l’angolo di rotazione.


Un nuovo paradigma

La complessità introdotta dal formalismo classico basato sull’algebra lineare con la sua miriade di micro-modelli e la sua Babele di linguaggi matematici diversi è necessaria?

Esiste un paradigma capace di unificare tutti questi micro-linguaggi in un contesto unico?


Una risposta ottimale:l’Algebra di Clifford

L’Algebra di Clifford (o Algebra geometrica) risponde pienamente al principio di Occam in quanto

Introduce un formalismo unico ed estremamente semplice.

Fornisce un modello semplificato e un linguaggio matematico unificante per la codifica della conoscenza.

Reinterpreta ed integra diversi linguaggi e termini scientifici in un unico contesto.


Due semplici postulati !

L’algebra di Clifford è fondata su questi due semplici postulati, ovvero gli assiomi del prodotto geometrico.

Le caratteristiche e le potenzialità dell’algebra derivano esclusivamente da questi due assiomi.


Prodotto geometrico

Dati due vettori a e b, il loro prodotto geometrico è la somma del prodotto interno ab e del prodotto esterno a∧b.

Il prodotto geometrico (o prodotto di Clifford) è il prodotto fondamentale introdotto da Clifford, dal quale è possibile derivare tutti gli altri prodotti.


Prodotto geometrico


a0 a1 a2 a3

b0

b1

b2

b3

ab = (a0b0+a1b1+a2b2+a3b3) +

(a0b1 – a1b0)e0e1+

(a0b2 – a2b0)e0e2 +

(a0b3 – a3b0)e0e3 +

(a1b2 – a2b1)e1e2 +

(a1b3 – a3b1)e1e3 +

(a2b3 – a3b2)e2e3

a = a0e0+a1e1+a2e2+a3e3b = b0e0+b1e1+b2e2+b3e3

scalare bivettore

Prodotto interno eprodotto esterno

Il prodotto interno di due vettori coincide con il classico prodotto scalare.

Il prodotto esterno (o wedge product) di due vettori può essere interpretato geometricamente come un segmento di piano orientato ed è chiamato bivettore.

A differenza del prodotto vettoriale a × b, il prodotto esterno è definito per qualsiasi dimensione.


BladesIl prodotto esterno di tre vettori può essere

interpretato geometricamente come un elemento di volume orientato ed è chiamato trivettore.

In generale, il prodotto esterno di k vettori è un sottospazio orientato a k dimensioni ed è chiamato blade di grado k o k-blade.


a∧b∧c

MultivettoriIn uno spazio ad n dimensioni le blades sono in

tutto 2n, mentre il numero di blades di grado k è pari a

Gli elementi generali dell’algebra di Clifford sono detti multivettori.

Il multivettore dell’algebra di Clifford ad n dimensioni è una combinazione lineare con coefficienti reali delle 2n blades di base.

Nello spazio 2D il multivettore ha la forma:


Codifica binaria delle blades


Il prodotto geometrico di due blades è lo XOR delle due maschere di bit corrispondenti

Esempio:

e0e1 * e1e2e3 = e0e2e3

0011 1110 = 1101

Blades 4D

Maschera di bit

1 0000

e0 0001

e1 0010

e0e1 0011

e2 0100

e0e2 0101

e1e2 0110

e0e1e2 0111

e3 1000

e0e3 1001

e1e3 1010

e0e1e3 1011

e2e3 1100

e0e2e3 1101

e1e2e3 1110

e0e1e2e3 1111

Prodotto geometrico

Qual è il significato geometrico del prodotto geometrico?

Se a e b sono ortogonali (ab=0)

Se a e b sono collineari (a∧b=0)

Il prodotto geometrico dà una misura della direzione relativa di due vettori.Commutatività => Vettori collineariAnticommutatività => Vettori ortogonali


Numeri complessi

L’algebra dei numeri complessi è isomorfa all’algebra di Clifford ad 1 dimensione con signature −

L’algebra dei numeri complessi è pure isomorfa alla sottoalgebra di grado pari dell’algebra di Clifford a 2 dimensioni con signature ++


Il bivettore i

La moltiplicazione per i ruota i vettori di un angolo retto:


QuaternioniL’algebra dei quaternioni è isomorfa all’algebra di

Clifford a 2 dimensioni con signature − −

L’algebra dei quaternioni è pure isomorfa alla sottoalgebra pari dell’algebra di Clifford a 3 dimensioni con signature +++


Riflessioni

Riflessione di un vettore a in un piano con normale m


RiflessioniDimostrazione

Pre-moltiplichiamo e post-moltiplichiamo a per m e invertiamo di segno

Essendo

si ottiene

da cui

Essendo ed m ortogonali e a|| ed m collineari,

si ha

da cui


Riflessioni

Dimostrazione (cont.)

Essendo m2 = 1

si ottiene

Ma

per cui


Rotazioni

La rotazione del vettore a si può ottenere attraverso due riflessioni in due piani con normali m ed n, dove il bivettore m∧n è il piano di rotazione e l’angolo θ tra i due vettori m ed n è la metà dell’angolo di rotazione.


Rotazione di un vettore a

Rotazioni

Prima riflessione

Seconda riflessione

da cui

è il rotore


Regola di CramerUtilizzando l’algebra di Clifford, si ottiene una

dimostrazione semplice e immediata della regola di Cramer per la soluzione di un sistema di equazioni lineari.

Sia dato un sistema di equazioni lineari:


Regola di CramerPre-moltiplichiamo e post-moltiplichiamo per

dove il pedice i indica l’assenza del termine

Semplificando in base alle regole del prodotto esterno, si ottiene:


Regola di CramerEssendo

con al posto di

si ottiene

che è proprio la regola di Cramer.


Equazioni di Maxwell


ρ☐ Hxy Hxz Ext

-Hxy ρ☐ Hyz Eyt

-Hxz -Hyz ρ☐ Ezt

-Ext -Eyt -Ezt ρ☐

Algebra dello spazio-tempo ovvero

Algebra di Clifford 4Dcon metrica di Minkowski

Le 4 equazioni di Maxwell si riducono ad una sola.

ρ☐ è la quadridensità di carica

simile all’equ. di Dirac con m = 0

J☐ è la quadricorrente

Equazione di Dirac


Applicazioni dell’algebra di Clifford


Un po’ di storia

W. K. Clifford, “On the Classification of Geometric Algebras”, Mathematical Papers, R. Tucker, ed., pp. 397-401, Macmillian, 1882.


William K. Clifford (1845-1879)

Hermann Grassmann (1809-1877)

David Hestenes (1933-)

William R. Hamilton (1805-1865)

D. Hestenes, “New Foundations for Classical Mechanics”, Kluwer Academic, 1986.

D. Hestenes, G. Sobczyk, “Clifford Algebra to Geometric Calculus: A Unified Language for Mathematics and Physics”, Kluwer Academic, 1987.

D. Hestenes, “Oersted Medal Lecture 2002: Reforming the Mathematical Language of Physics”.

Un po’ di storia (2)


Leo Dorst

Stephen Mann

L. Dorst, S. Mann, “Geometric Algebra: A Computational Framework for Geometrical Applications (Part 1: Algebra),” IEEE Computer Graphics and Applications, vol. 22, no. 3, pp. 24-31, May/June 2002.

L. Dorst, S. Mann, “Geometric Algebra: A Computational Framework for Geometrical Applications (Part 2: Applications),” IEEE Computer Graphics and Applications, vol. 22, no. 4, pp. 58-67, July/Aug. 2002.

L. Dorst, D. Fontijne, S. Mann, “Geometric Algebra for Computer Science: An Object Oriented Approach to Geometry”, Morgan Kaufmann, 2007.

Ambiti applicativi


Algebra di Clifford

Computer grafica

Visione artificiale

Robotica

Elaborazione di immagini

Coprocessori grafici innovativi

Le attuali schede video utilizzano, per le elaborazioni grafiche tridimensionali, i modelli geometrici tradizionali basati sull’algebra lineare e sui calcoli matriciali.

Il nuovo paradigma fondato sull’algebra di Clifford consente lo sviluppo di coprocessori grafici innovativi.


L’algebra di Clifforde la computer grafica

Per le applicazioni grafiche si utilizzano le algebre di Clifford 4D e 5D.

Le algebre di Clifford 4D e 5D rappresentano i modelli più potenti della geometria euclidea tridimensionale:Modello omogeneo (coordinate omogenee)Modello conforme


Modello omogeneo(coordinate omogenee)

Algebra di Clifford 4D

Modello conforme Algebra di Clifford 5D

Il modello omogeneo


22

33

44

11

L’intersezione di due rette si

ottiene applicando

semplicemente l’operatore “meet” ai due

bivettori

Gli oggetti geometrici

sono rappresentati direttamente dagli elementi dell’algebra

4D

Il modello conforme


Punto= c ∧ ∞Retta= a ∧ c ∧ ∞Cerchio= a ∧ b ∧ cPiano= a ∧ b ∧ c ∧ ∞Sfera= a ∧ b ∧ c ∧ d

Tutti gli oggetti geometrici (compresi cerchi e sfere)

sono rappresentati direttamente dagli

elementi dell’algebra 5D

Tutte le operazioni geometriche conformi (rotazioni, traslazioni,

dilatazioni) si ottengono attraverso il prodotto

geometrico con operatori detti versori

X può essere di qualsiasi dimensione !

Implementazioni dell’algebra di Clifford

Lo sviluppo di coprocessori grafici basati sull’algebra di Clifford richiede la ricerca di implementazioni efficienti dal punto di vista computazionale delle algebre di Clifford 4D e 5D

Implementazioni esistenti: Implementazioni software Implementazioni hardware


Algebra di Clifford 4D

Un generico multivettore dell’algebra di Clifford 4D contiene 24 = 16 blades, dove ogni blade è una coppia coefficiente-blade di base

Come è possibile rappresentare le blades del generico multivettore?


m = s0+

a0e0+a1e1+a2e2+a3e3+

a01e0e1+a02e0e2+a03e0e3+a12e1e2+a13e1e3+a23e2e

3+

a012e0e1e2+a013e0e1e3+a023e0e2e3+a123e1e2e3+

a0123e0e1e2e3

Codifica binaria delle blades

Il prodotto geometrico di due blades è lo XOR delle due maschere di bit corrispondenti

Esempio:

e0e1 * e1e2e3 = e0e2e3

0011 1110 = 1101


Blades 4D

Maschera di bit

1 0000

e0 0001

e1 0010

e0e1 0011

e2 0100

e0e2 0101

e1e2 0110

e0e1e2 0111

e3 1000

e0e3 1001

e1e3 1010

e0e1e3 1011

e2e3 1100

e0e2e3 1101

e1e2e3 1110

e0e1e2e3 1111

Una rappresentazione orientata all’hardware

Qual è la migliore rappresentazione degli elementi dell’algebra di Clifford nell’ottica di una esecuzione delle operazioni di Clifford direttamente in hardware?

La rappresentazione naturale, basata sugli elementi omogenei, ha il difetto di utilizzare elementi di dimensione variabile.


Elementi omogeneispazio 4D


BladesElemento omogeneo

1 scalare (s)

e0 e1 e2 e3 vettore (v)

e0e1 e0e2 e0e3 e1e2 e1e3 e2e3 bivettore (b)

e1e2e3

e0e2e

3

e0e1e

3

e0e1e

2

trivettore (t)

e0e1e2e

3pseudoscalare (p)

multivettore 4D – rappresentazione basata su elementi omogenei

m = (s, v, b, t, p)

Necessità di una rappresentazione più compatta

Blades

1

e0

e1

e2

e3

e0e1

e0e2

e0e3

e1e2

e1e3

e2e3

e0e1e2

e0e1e3

e0e2e3

e1e2e3

e0e1e2e3

Una rappresentazione di dimensione fissa

Qual è il modo ottimo di posizionare le 16 blades del multivettore 4D in una matrice 4x4?


1

e0

e1

e2

e3

e0e1

e0e2

e0e3

e1e2

e1e3

e2e3

e0e1e2

e0e1e3

e0e2e3

e1e2e3

e0e1e2e3

24 42

?

Dalle blades alle quadruplette


BladesQuadruplet

ta

e0 e1 e2 e3 V

e1e2e3

e0e2e

3

e0e1e

3

e0e1e

2

T

1 e0e1 e0e2 e0e3 S

e0e1e2e

3

e2e3 e1e3 e1e2 P

vettorescalare

trivettore

bivettore

pseudoscalare

multivettore 4D – rappresentazione basata su quadruplette

m = (V, T, S, P)

Blades

1

e0

e1

e2

e3

e0e1

e0e2

e0e3

e1e2

e1e3

e2e3

e0e1e2

e0e1e3

e0e2e3

e1e2e3

e0e1e2e3

Quadruplette - Vantaggi

Elementi di dimensione fissa

Architettura hardware compatta e veloce


Semplificazione delle operazioni algebriche

Il prodotto di due quadruplette dà come risultato la somma di due quadruplette

Tutte le operazioni di prodotto possono essere ricondotte ad un’unica operazione: prodotto di due vettori V



V 0001 0010 0100 1000

T 1110 1101 1011 0111

S 0000 0011 0101 1001

P 1111 1100 1010 0110

V e0 e1 e2 e3

T e1e2e3 e0e2e3 e0e1e3 e0e1e2

S 1 e0e1 e0e2 e0e3

P e0e1e2e3 e2e3 e1e3 e1e2

XOR con 1111

XOR con 0001

XOR con 1110

T, S e P possono essere ottenute attraverso operazioni XOR tra V e opportune maschere di bit

I = e0e1e2e3 1111

W = e0 0001

Z = e1e2e3 1110

Maschere di bit


Il prodotto di due quadruplette dà come risultato la somma di due quadruplette

Formato unico per i dati di input e di output


* V T S P

V S + P S + P V + T V + T

T S + P S + P V + T V + T

S V + T V + T S + P S + P

P V + T V + T S + P S + P

Quadruplette - Vantaggi Tutte le operazioni di prodotto tra due quadruplette di qualsiasi tipo

possono essere ricondotte ad un prodotto tra due vettori


T S

Pre-processing Pre-processing

IrT=V V=SW

Vector_Product

S + P

Post-processing

I (S + P) Wr

4 4

4 4

4 4+

4 4+

Le due quadruplette sono trasformate in due vettori attraverso uno stadio di pre-processing che consiste in semplici cambiamenti di segno dei coefficienti

Si esegue il prodotto geometrico dei due vettori

Le due quadruplette del risultato sono ottenute attraverso uno stadio di post-processing che consiste in semplici operazioni di cambiamenti di segno e/o swapping

Esempio


a0 a1 a2 a3T

- a0 a1 - a2 a3V = IrT

b0 b1 b2 b3

b0 - b1 - b2 - b3

S

SW = V

c0 c1 c2 c3 c4 c5 c6 c7

V * V

c4 c5 - c6 c7 - c0 - c1 c2 - c3

Pre-processing solo cambiamenti di segno

Post-processing solo cambiamenti di segno e swapping

Esempio: T*S

Conclusioni

La rappresentazione semplificata basata sull’uso delle quadruplette ha consentito lo sviluppo di un’architettura hardware veloce e compatta.

E’ stata progettata e realizzata una famiglia di architetture dedicate per l’esecuzione nativa delle operazioni di Clifford 4D e 5D.

I risultati sperimentali hanno mostrato un significativo aumento delle prestazioni rispetto all’esecuzione su processori general-purpose tradizionali.


Bibliografia D. Hestenes, “New Foundations for Classical Mechanics”, Kluwer Academic,

1986.

D. Hestenes, G. Sobczyk, “Clifford Algebra to Geometric Calculus: A Unified Language for Mathematics and Physics”, Kluwer Academic, 1987.

D. Hestenes, “Oersted Medal Lecture 2002: Reforming the Mathematical Language of Physics”.

L. Dorst, S. Mann, “Geometric Algebra: A Computational Framework for Geometrical Applications (Part 1: Algebra),” IEEE Computer Graphics and Applications, vol. 22, no. 3, pp. 24-31, May/June 2002.

L. Dorst, S. Mann, “Geometric Algebra: A Computational Framework for Geometrical Applications (Part 2: Applications),” IEEE Computer Graphics and Applications, vol. 22, no. 4, pp. 58-67, July/Aug. 2002.

L. Dorst, D. Fontijne, S. Mann, “Geometric Algebra for Computer Science: An Object Oriented Approach to Geometry”, Morgan Kaufmann, 2007.

Silvia Franchini, Giorgio Vassallo, Filippo Sorbello, “A brief introduction to Clifford algebra”, Rapporto tecnico N. 2/2010, Dipartimento di Ingegneria Informatica - Università degli Studi di Palermo, 2010, http://www.dinfo.unipa.it/~franchini/CliffTechRep.pdf.


Bibliografia Silvia Franchini, Antonio Gentile, Filippo Sorbello, Giorgio Vassallo,

Salvatore Vitabile, “Design and implementation of an embedded coprocessor with native support for 5D, quadruple-based Clifford algebra”, IEEE Transactions on Computers, Vol. 62, No. 12, pp. 2366-2381, 2013.

Silvia Franchini, Antonio Gentile, Filippo Sorbello, Giorgio Vassallo, Salvatore Vitabile, “Design Space Exploration of Parallel Embedded Architectures for Native Clifford Algebra Operations”, IEEE Design and Test of Computers, Volume 29, Issue 3, May-June 2012, pp. 60-69.

Silvia Franchini, Antonio Gentile, Filippo Sorbello, Giorgio Vassallo, Salvatore Vitabile, “Fixed-size Quadruples for a New, Hardware-Oriented Representation of the 4D Clifford Algebra”, “Advances in Applied Clifford Algebras”, Volume 21, Issue 2, June 2011, pag. 315-340, Springer Basel AG.

Silvia Franchini, Antonio Gentile, Filippo Sorbello, Giorgio Vassallo, Salvatore Vitabile, “An Embedded, FPGA-based Computer Graphics Coprocessor with Native Geometric Algebra Support”, Integration, The VLSI Journal, Vol. 42, No. 3, June 2009, pp. 346-355, ISSN: 0167-9260, doi: 10.1016/j.vlsi.2008.09.010.


L’algebra di Clifford e il rasoio di Occam Giorgio Vassallo Silvia Franchini Seminario di Logica e...

Documents

Transcript of L’algebra di Clifford e il rasoio di Occam Giorgio Vassallo Silvia Franchini Seminario di Logica e...