Fast algorithms for floating-point interval matrix multiplication

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:236

Article

Ozaki, Katsuhisa^1,4  Ogita, Takeshi^2,4  Rump, Siegfried M.^3,5  Oishi, Shin'ichi^3,4 

[1] Shibaura Inst Technol, Coll Syst Engn & Sci, Dept Math Sci, Minuma Ku, Saitama 3378570, Japan

[2] Tokyo Womans Christian Univ, Dept Math Sci, Suginami Ku, Tokyo 1678585, Japan

[3] Waseda Univ, Fac Sci & Engn, Shinjyuku Ku, Tokyo 1698555, Japan

[4] CREST, JST Japan Sci & Technol Agcy, Tokyo, Japan

[5] Hamburg Univ Technol, Inst Reliable Comp, D-21071 Hamburg, Germany

关键词: Matrix multiplication;    Interval arithmetic;    Verified numerical computations;    INTLAB;   

DOI  :  10.1016/j.cam.2011.10.011

来源: Elsevier

【 摘 要 】

We discuss several methods for real interval matrix multiplication. First, earlier studies of fast algorithms for interval matrix multiplication are introduced: naive interval arithmetic, interval arithmetic by midpoint-radius form by Oishi-Rump and its fast variant by Ogita-Oishi. Next, three new and fast algorithms are developed. The proposed algorithms require one, two or three matrix products, respectively. The point is that our algorithms quickly predict which terms become dominant radii in interval computations. We propose a hybrid method to predict which algorithm is suitable for optimizing performance and width of the result. Numerical examples are presented to show the efficiency of the proposed algorithms. (C) 2011 Elsevier B.V. All rights reserved.

【 授权许可】

Free