Fast Chaotic Artificial Time Integration

Uri Ascher () and Kees van den Doel ()
Additional contact information
Uri Ascher: University of British Columbia, Department of Computer Science
Kees van den Doel: University of British Columbia, Department of Computer Science

A chapter in The Courant–Friedrichs–Lewy (CFL) Condition, 2013, pp 147-155 from Springer

Abstract: Abstract Gradient descent methods for large positive definite linear and nonlinear algebraic systems arise when integrating a PDE to steady state and when regularizing inverse problems. However, these methods may converge very slowly when utilizing a constant step size, or when employing an exact line search at each step, with the iteration count growing proportionally to the condition number. Faster gradient descent methods must occasionally resort to significantly larger step sizes, which in turn yields a strongly nonmonotone decrease pattern in the residual vector norm. In fact, such faster gradient descent methods generate chaotic dynamical systems for the normalized residual vectors. Very little is required to generate chaos here: simply damping steepest descent by a constant factor close to 1 will do. The fastest practical methods of this family in general appear to be the chaotic, two-step ones. Despite their erratic behavior, these methods may also be used as smoothers, or regularization operators. Our results also highlight the need for better theory for these methods.

Keywords: Gradient descent; Artificial time integration; Dynamical system; Stability; Chaos; Regularization (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-0-8176-8394-8_10

Ordering information: This item can be ordered from
http://www.springer.com/9780817683948

DOI: 10.1007/978-0-8176-8394-8_10

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().