|
Article information
2025 , Volume 30, ¹ 2, p.73-86
Rozinov S.V.
Precision control with ball arithmetic in the conjugate gradient method using the example of an unconditional quadratic optimization problem
Purpose. Developing a tool with precision tracking for solving ill-conditioned quadratic unconditional optimization problems of enlarged dimension. Methodology. The standard conjugate gradient (CG) method was chosen as the basis of the algorithm for finding the solution. The work uses the ball arithmetic (van der Hoeven, Johansson), which provides convenient tools for operations with arbitrary precision numbers, as well as vectors and matrices based on them. The precision indicators of ball numbers and composite numeric objects in bits and decimal digits are described. A centering procedure is proposed to speed up calculations in iterations of the CG algorithm. Computational experiments have been carried out to illustrate the precision degradation process in CG iterations and to find out mantissa length of ball numbers required to successfully find a solution to a number of ill-conditioned quadratic unconditional optimization problems. The effect of centering on the total solution time has been examined experimentally. Findings. The pattern of the precision degradation in the computing process is different and significantly depends on the type of quadratic problem. According to the results of the computational experiment, the centering significantly reduces the time for finding solution to the optimization problems under consideration. A hybrid CG algorithm with a feedback mechanism using centering in a precision depletion situation of intermediate data is proposed. Value. The proposed approach along with the hybrid CG algorithm allows obtaining stable and time-acceptable solutions for several types of poorly conditioned quadratic unconditional optimization problems of enlarged dimension.
[link to elibrary.ru]
Keywords: conjugate gradient method, quadratic optimization, interval computation, ill-conditioned optimization problem, ball arithmetic, multiple precision arithmetic
doi: 10.25743/ICT.2025.30.2.006
Author(s):
Rozinov Sergei Vladimirovich
Position: Junior Research Scientist
Office: Institute of Siberian Branch of the Russian Academy of Sciences
Address: 664033, Russia, Irkutsk, Lermontova str, 130
E-mail: rozinov74@gmail.com
References:
1. Shary S.P. Konechnomernyy interval’nyy analiz [Finite-dimensional interval analysis]. Novosibirsk:
Izdatel’stvo “XYZ”; 2022: 654. (In Russ.)
2. van der Hoeven J. Ball arithmetic. Technical Report, HAL 00432152. 2011. Available at: http:
//hal.archives-ouvertes.fr/hal-00432152/fr/.
3. Rump S.M. Verification methods: rigorous results using floating-point arithmetic. Acta Numerica.
2010; 287–449.
4. Nesterov Yu.E. Metody vypukloy optimizatsii [Methods for convex optimization]. Moscow: Izdatel’
stvo MTsNMO; 2010: 67–72. (In Russ.)
5. Konnov I.V. Nelineynaya optimizatsiya i variatsionnye neravenstva [Nonlinear optimization and
variational inequalities]. Kazan: Kazanskiy Universitet; 2013: 508. (In Russ.)
6. Pytlak R. Conjugate gradient algorithms in nonconvex optimization. Nonconvex Optimization and
Its Applications. Springer-Verlag, Berlin, Heidelberg; 2009: 477. DOI:10.1007/978-3-540-85634-4.
7. Johansson F. Arb: efficient arbitrary-precision midpoint-radius interval arithmetic. IEEE Transacti
ons on Computers. 2017; 66(8):1281–1292.
8. Johansson F. Arb: a C library for ball arithmetic. ACM Communications in Computer Algebra.
2013; 47(4):166–169.
9. Johansson F. Ball arithmetic as a tool in computer algebra. Communications in Computer and
Information Science. 2020; (1125):334–336. DOI:10.1007/978-3-030 41258-6_26.
10. Hart W.B. Fast library for number theory: an introduction. Proceedings of the Third International
Congress Conference on Mathematical Software, ICMS’10. Springer-Verlag, Berlin, Heidelberg; 2010;
88–91.
11. Revol N., Rouillier F. Motivations for an arbitrary precision interval arithmetic and the MPFI
library. Reliable Computing. 2005; 11(4):275–290.
12. Beckermann B. The condition number of real Vandermonde, Krylov and positive definite Hankel
matrices. Numerische Mathematik. 2000; 85(4):553–577
Bibliography link:
Rozinov S.V. Precision control with ball arithmetic in the conjugate gradient method using the example of an unconditional quadratic optimization problem // Computational technologies. 2025. V. 30. ¹ 2. P. 73-86
|
