Iterative Methods and Preconditioning for Large and Sparse Linear Systems with Applications

È stata una fatica improba, ma finalmente è uscito!

Dalla quarta di copertina:

This book describes, in a basic way, the most useful and effective iterative solvers and appropriate preconditioning techniques for some of the most important classes of large and sparse linear systems.

The solution of large and sparse linear systems is the most time-consuming part for most of the scientific computing simulations. Indeed, mathematical models become more and more accurate by including a greater volume of data, but this requires the solution of larger and harder algebraic systems. In recent years, research has focused on the efficient solution of large sparse and/or structured systems generated by the discretization of numerical models by using iterative solvers.

Potete acquistarlo su Amazon

Quante regine su di una scacchiera?

[singlepic id=111 w=404 h=303 float=center]
(Luigi Mussini – “Sfida scacchistica alla corte del Re di Spagna” (1883))

Storia di un campione di scacchi.

Il gioco degli scacchi è antico, molto antico, tuttavia non smette di affascinare. Ad esempio nel quadro del Mussini che apre l’articolo è ricordata la vittoria scacchistica di Giò Leonardo Di Bona alla corte di Filippo II, Re di Spagna. Questa è una storia che proviene da lontano. Era il 1560 e il giovane Leonardo si trovò a giocare a Roma contro Ruy Lopez. Fù una sconfitta, ma egli dimostrò una predispozione e una mente adatta al gioco degli scacchi, una trascrizione di quello che resta della partita si trova qui). Dopo questa prima sconfitta si trasferisce a Napoli e lì inizia a studiare il gioco, diventa bravo, molto bravo. Tanto da raggiungere il livello necessario a sfidare il campione italiano: Paolo Boi, detto il Siracusano. Anche questa volta Giò subisce una sconfitta, tuttavia le sue abilità sono molto cresciute. Il giovane scacchista, detto il “puttino”, decise di far ritorno nel suo paese natale: Cutro. Quando vi giunse trovò ad aspettarlo una triste notizia, suo fratello era stato rapito da alcuni pirati saraceni. Leonardo decide di sfidare a scacchi il comandante dei pirati per ottenere il rilascio del fratello, questi accetta e viene sconfitto dal giovane, così il puttino torna a casa con la vita di suo fratello e 200 ducati, una cifra ragguardevole per l’epoca, ottenuti dal pirata in segno di ammirazione per le sue abilità. Nel 1574 Leonardo iniziò a viaggiare per l’Europa. A Madrid ebbe occasione di incontrare una sua vecchia conoscenza, il cardinale Ruy Lopez. Questa volta la sfida fra i due si celebrò di fronte a Filippo II di Spagna avendo un nuovo esito, Leonardo riuscì a sconfiggere il cardinale, qui e qui le trascrizioni di ciò che resta della partita,  e venne insignito dal Re del titolo di Campione di Scacchi d’Europa. Oltre l’onorificenza, Filippo tentò di retribuire con moneta sonante l’impresa dello scacchista, tuttavia questi rifiutò e chiedendo in cambio che il suo paese Cutro si vedesse riconosciuto lo status di Città e venisse esentato dal pagamento delle tasse per vent’anni. Dopo questo periodo felice il campione di scachi è costretto a fare ritorno a Cutro a causa del precario stato di salute della moglie, che muore prima che lui possa raggiungerla.  Dopo questo lutto venne invitato dal re di Portogallo per giocare contro uno scacchista arabo che sconfigge facilmente inaugurando così un periodo di rinnovata felicità, che, tuttavia, non era destinato a durare. Nel 1597 alla corte del principe di Bisignano, un paese oggi in provincia di Cosenza, morì avvelenato da un avversario invidioso del suo successo.

Regine e scacchiere.

Il gioco di cui voglio parlare è base di scacchi, ma in una variante più matematica, ovvero, volendo darne una formulazione:

“Come si possono disporre n regine su di una scacchiera nxn senza che nessuna di esse sia in posizione tale da poter mangiarne un’altra in una sola mossa?”

[singlepic id=114 w=200 h=200 float=right] Per prima cosa diamo una rispolverata a come può muoversi una regina usando l’agevole illustrazione presa dalle Regole degli scacchi FIDE. La soluzione di questo problema è dovuta a S. Günther, per chi fosse interessato ad una biografia la trova qui, e si basa sull’uso del determinante di una matrice con cui rappresentare la scacchiera. Per prima cosa si deve costruire la matrice nel seguente modo:
[singlepic id=116 w=267 h=158 float=center]
Ovvero, facendo sì che stesso simbolo e stesso indice giacciano lungo le traiettorie dell’alfiere, ovvero le diagonali. Per calcolare il determinante di questa matrice poi facciamo riferimento alla formula di Leibniz (anche nota come formula esplicita per il calcolo del determinante):
[singlepic id=117 w=257 h=56 float=center]
Ogni termine in questa formula contiene uno ed un solo elemento di ogni riga ed uno ed un solo elemento di ogni colonna, questo fa sì che è sufficiente scegliere il termine in cui ogni lettera e ogni suffisso non appaiono più di una volta. Questa sarà la configurazione adatta! Tuttavia c’è un problema, partendo direttamente dalla classica scacchiera 8×8 il termine da cercare, una volta calcolato il determinante, sarà in mezzo a 8!… 8! è un numero abbastanza elevato, è infatti uguale a 8!=8x7x6x5x4x3x2x1=40320. Cercare di attaccare direttamente il problema in questo modo è laborioso, pieno di calcoli e richiede un tempo elevato. Una strategia migliore è quella di partire dalla prima scacchiera in cui il problema è risolvibile, ovvero una scacchiera 4×4 e, determinata una soluzione in quel caso, aggiungere ogni volta una riga e una colonna ampliando la soluzione di partenza. Questo è fattibile poiché 4!=24, quindi i termini da cercare non sono poi tanti. In questa maniera si riesce ad ottenere una soluzione della 8×8, ad esempio:

[singlepic id=118 w=350 h=350 float=center]

Una lista del numero di soluzioni, a meno di simmetrie della scacchiera, è:

Dim. Scacchiera 4×4 5×5 6×6 7×7 8×8 9×9 10×10
N° Soluzioni 1 2 1 6 12 46 92

Auguro un buon divertimento a tutti quelli che vorranno andare a caccia delle altre soluzioni!

Link, fonti, materiale vario.