| dbo:abstract
|
- ABS methods, where the acronym contains the initials of Jozsef Abaffy, Charles G. Broyden and Emilio Spedicato, have been developed since 1981 to generate a large class of algorithms for the following applications:
* solution of general linear algebraic systems, determined or underdetermined,
* full or deficient rank;
* solution of linear Diophantine systems, i.e. equation systems where the coefficient matrix and the right hand side are integer valued and an integer solution is sought; this is a special but important case of Hilbert's tenth problem, the only one in practice soluble;
* solution of nonlinear algebraic equations;
* solution of continuous unconstrained or constrained optimization. At the beginning of 2007 ABS literature consisted of over 400 papers and reports and two monographs, one due to Abaffy and Spedicato and published in 1989, one due to Xia and Zhang and published, in Chinese, in 1998. Moreover three conferences had been organized in China. Research on ABS methods has been the outcome of an international collaboration coordinated by Spedicato of University of Bergamo, Italy. It has involved over forty mathematicians from Hungary, UK, China, Iran and other countries. The central element in such methods is the use of a special matrix transformation due essentially to the Hungarian mathematician Jenő Egerváry, who investigated its main properties in some papers that went unnoticed. For the basic problem of solving a linear system of m equations in n variables, where , ABS methods use the following simple geometric idea: 1.
* Given an arbitrary initial estimate of the solution, find one of the infinite solutions, defining a linear variety of dimension n − 1, of the first equation. 2.
* Find a solution of the second equation that is also a solution of the first, i.e. find a solution lying in the intersection of the linear varieties of the solutions of the first two equations considered separately. 3.
* By iteration of the above approach after m' steps one gets a solution of the last equation that is also a solution of the previous equations, hence of the full system. Moreover it is possible to detect equations that are either redundant or incompatible. Among the main results obtained so far:
* unification of algorithms for linear, nonlinear algebraic equations and for linearly constrained nonlinear optimization, including the LP problem as a special case;
* the method of Gauss has been improved by reducing the required memory and eliminating the need for pivoting;
* new methods for nonlinear systems with convergence properties better than for Newton method;
* derivation of a general algorithm for Hilbert tenth problem, linear case, with the extension of a classic Euler theorem from one equation to a system;
* solvers have been obtained that are more stable than classical ones, especially for the problem arising in primal-dual interior point method;
* ABS methods are usually faster on vector or parallel machines;
* ABS methods provide a simpler approach for teaching for a variety of classes of problems, since particular methods are obtained just by specific parameter choices. Knowledge of ABS methods is still quite limited among mathematicians, but they have great potential for improving the methods currently in use. (en)
- In matematica, i metodi ABS, dove la sigla sta per le iniziali dei cognomi di , ed Emilio Spedicato, sono metodi computazionali sviluppati a partire dal 1981 al fine di generare una vasta classe di algoritmi utilizzabili per le seguenti applicazioni:
* Soluzione di sistemi lineari algebrici generali, determinati o sottodeterminati, a rango pieno o deficiente.
* Soluzione di sistemi lineari diofantei, sistemi di equazioni lineari nei quali la matrice ed il termine noto hanno componenti intere e si cerca una soluzione ad interi. Questo è un caso particolare, ma importante ed in pratica l'unico risolubile, del decimo problema di Hilbert.
* Soluzione di equazioni algebriche non lineari.
* Soluzione di problemi di ottimizzazione continua vincolata e non vincolata. All'inizio del 2007 su questi argomenti erano stati prodotti oltre 400 articoli e rapporti e due monografie, una nel 1989 di Abaffy e Spedicato, una nel 1998 di Xia e Zhang. Tre convegni erano stati organizzati in Cina. La ricerca sui metodi ABS è stata il frutto di una collaborazione internazionale sviluppata a partire dal 1981, coordinata da Spedicato dell'Università di Bergamo e coinvolgente una quarantina di matematici cinesi, iraniani, ungheresi, inglesi, italiani e di altri paesi. Elemento cruciale nei metodi ABS è l'utilizzo di una speciale trasformazione matriciale dovuta essenzialmente al matematico ungherese , che ne studiò le proprietà fondamentali in alcuni articoli che passarono tuttavia quasi inosservati. Relativamente alla soluzione dei sistemi lineari di m equazioni in n variabili, con m ≤ n, i metodi ABS sono basati su una semplice idea di natura geometrica, ovvero: 1.
* Data una arbitraria stima iniziale della soluzione, determinare una delle infinite soluzioni, definenti una varietà lineare di dimensione n-1, della prima equazione. 2.
* Individuare una determinata soluzione della seconda equazione che sia anche soluzione della prima e quindi giaccia nella intersezione delle varietà lineari delle soluzioni delle prime due equazioni separatamente considerate. 3.
* Iterando il procedimento si perviene dopo m passi ad una soluzione dell'ultima equazione che è anche soluzione delle precedenti, e quindi il sistema è risolto. Nel corso del processo è possibile identificare le eventuali equazioni ridondanti, che sono rimosse, o le eventuali equazioni incompatibili, che rendono il sistema non risolubile. Fra i risultati sinora ottenuti vanno ricordati i seguenti.
* Unificazione degli algoritmi per sistemi lineari, non lineari ed ottimizzazione vincolata (problema LP come caso particolare).
* Miglioramento del metodo di Gauss grazie a una riduzione della memoria richiesta e alla eliminazione della necessità di pivoting; tale algoritmo ABS ha naturale applicazione al metodo del simplesso in programmazione lineare, per il quale riduce memoria e complessità.
* Ottenimento di nuovi metodi per sistemi non lineari con migliori proprietà di convergenza del metodo di Newton.
* Individuazione di un algoritmo generale per la soluzione del decimo problema di Hilbert nel caso lineare, con prima estensione di un classico teorema di Eulero da una equazione ad un sistema.
* Ottenimento di solutori più stabili per varie classi di problemi, in particolare per il metodo interior point primale-duale.
* Ottenimento di metodi più veloci su computer vettoriali o paralleli.
* Semplificazione a livello didattico di interi campi dell'analisi numerica, dove i vari metodi proposti e tutti quelli possibili, sono visti come caso particolare di una classe generale ottenuta con un approccio intuitivo e geometrico. La conoscenza dei metodi ABS è ancora poco diffusa; tuttavia resta il loro potenziale per apportare sostanziali miglioramenti a vari metodi finora usati. (it)
|
| rdfs:comment
|
- ABS methods, where the acronym contains the initials of Jozsef Abaffy, Charles G. Broyden and Emilio Spedicato, have been developed since 1981 to generate a large class of algorithms for the following applications: At the beginning of 2007 ABS literature consisted of over 400 papers and reports and two monographs, one due to Abaffy and Spedicato and published in 1989, one due to Xia and Zhang and published, in Chinese, in 1998. Moreover three conferences had been organized in China. Among the main results obtained so far: (en)
- In matematica, i metodi ABS, dove la sigla sta per le iniziali dei cognomi di , ed Emilio Spedicato, sono metodi computazionali sviluppati a partire dal 1981 al fine di generare una vasta classe di algoritmi utilizzabili per le seguenti applicazioni: All'inizio del 2007 su questi argomenti erano stati prodotti oltre 400 articoli e rapporti e due monografie, una nel 1989 di Abaffy e Spedicato, una nel 1998 di Xia e Zhang. Tre convegni erano stati organizzati in Cina. Fra i risultati sinora ottenuti vanno ricordati i seguenti. (it)
|
