Cholesky分解递归算法与改进1
需积分: 0 70 浏览量
2022-08-04
00:45:45
上传
评论
收藏 525KB PDF 举报
第 38 卷 第 8 期
2001 年 8 月
计 算 机 研 究 与 发 展
JOU RNAL O F COM PU TER RESEARCH & D EV ELO PM EN T
Vo l138,No18
A ug. 2001
原稿收到日期: 2000210210; 修改稿收到日期: 2001203228
本课题得到江苏省教育厅留学回国人员科研启动经费项目基金资助
Cholesky
分解递归算法与改进
陈建平
①
Jerzy W asniew ski
②
①
(
南通工学院信息工程系 南通 226007
)
②
(
丹麦研究与教育计算中心 哥本哈根
DK
22800
)
(
chen
.
jp
@
ntit
.
edu
.
cn
)
摘 要 递归算法是计算稠密线性代数的一种新的有效方法. 递归产生自动、变化的矩阵分块, 能充分发挥当今分
级存储高性能计算机的效率. 对
Cholesky
分解递归算法进行了研究, 给出了算法的详细推导过程, 用具有递归功
能的
Fo rtran
90 实现了算法, 并通过矩阵元素顺序重排的方法, 进一步提高了递归算法的运算速度. 研究产生的算
法比目前常用的分块算法快 15%～ 25%.
关键词 数值计算, 递归, 矩阵分块, 分级存储,
Fo rtran
90
中图法分类号
TP
301
RECURSIVE AL GORITHM AND IM PROVEM ENT FOR
CHOLESKY FACTORIZATION
CH EN J ian
2
Ping
①
and Jerzy W asniew ski
②
①
(
D ep artm ent of Inf orm ation E ng ineering
,
N antong Institute of T echnology
,
N antong
, 226007
)
②
(
D anish Comp uting Center f or R esearch and Education
,
L y ng by
,
D enm ark
,
D K
22800
)
Abstract
Recursion is a new effective m ethod fo r computing dense linear algebra
.
It allow s for
efficient utilization of m emo ry hierarchies of today’s high
2
perform ance computers
.
The recursive
algorithm fo r Cho lesky facto rization is studied in this paper
.
A detailed derivation of the recursive
Cho lesky algorithm is given
.
The algorithm is then imp lem ented in Fo rtran
90
that suppo rts
recursion as a language feature
.
The efficiency of the recursive algorithm is further imp roved by
using a m ethod of m atrix elem ent reo rdering
.
The resulting algorithm s are
15%～ 25%
faster
than the currently used block algorithm
.
Key words
num erical computation
,
recursion
,
m atrix blocking
,
m emo ry hierarchy
,
Fo rtran
90
1 引 言
以
Cho lesky
分解、
LU
分解等为代表的线性代
数问题的数值计算在现代科学研究和工程技术中得
到广泛应用. 随着计算机结构和技术的发展, 实现这
些线性代数数值计算的计算机算法和软件也在不断
发展. 通用的基本线性代数子程序库
BLA S
(
basic
linear algebra subp rogram s
)
从 70 年代的
L evel
21
BLA S
(
执行向量2向量运算
)
, 发展到 80 年代的
L evel
22
BLA S
(
执行矩阵2向量运算
)
, 再到 90 年代
的
L evel
23
BLA S
(
执行矩阵2矩阵运算
)
[1]
. 以调用
BLA S
为核心运算的线性代数软件包也相应地从早
期的
L IN PACK
发展 到现 在 的
LA PACK
(
linear
algebra package
)
[2]
.
目前, 超标量、超流水线、具有多级存储结构的
高性能
R ISC
计算机已占据了数值计算领域的主导
地位.
RS IC
处理器的运算速度非常快, 它们与存储
评论0