Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Circumscribed ellipsoid algorithm for fixed-point problems
HTML articles powered by AMS MathViewer

by C. Boonyasiriwat, K. Sikorski and C. Tsay PDF
Math. Comp. 80 (2011), 1703-1723 Request permission


We present a new implementation of the almost optimal Circumscribed Ellipsoid (CE) Algorithm for approximating fixed points of nonexpanding functions, as well as of functions that may be globally expanding, however, are nonexpanding/contracting in the direction of fixed points. Our algorithm is based only on function values, i.e., it does not require computing derivatives of any order. We utilize the absolute and residual termination criteria with respect to the second norm. The numerical results confirm that the CE algorithm is much more efficient than the simple iteration algorithm whenever the Lipschitz constant is close to 1. We also compare it with the Newton-Raphson method. In some tests the Newton-Raphson method is more efficient than the CE method, especially when the problem size is large. However, the CE algorithm is an excellent method for low dimensional functions with discontinuities and/or low regularity. Our implementation can be downloaded from$\sim$sikorski/cea.
Similar Articles
Additional Information
  • C. Boonyasiriwat
  • Affiliation: School of Computing, University of Utah, 50 S. Central Campus Dr., Salt Lake City, Utah 84112
  • Email:
  • K. Sikorski
  • Affiliation: School of Computing, University of Utah, 50 S. Central Campus Dr., Salt Lake City, Utah 84112
  • Email:
  • C. Tsay
  • Affiliation: Computer Science and Information Management, Providence University 200 Chung-chi Rd., Shalu Taichung 43301, Taiwan
  • Email:
  • Received by editor(s): October 3, 2008
  • Received by editor(s) in revised form: April 23, 2010
  • Published electronically: November 30, 2010

  • Dedicated: We dedicate this paper to the memory of Leonid Khachiyan, collaborator and friend, who introduced the circumscribed ellipsoid algorithm as the first way of solving linear programming problems in polynomial time.
  • © Copyright 2010 American Mathematical Society
  • Journal: Math. Comp. 80 (2011), 1703-1723
  • MSC (2010): Primary 47H10, 65H10; Secondary 65Y20, 68Q25
  • DOI:
  • MathSciNet review: 2785475