A backward error analysis of a null space algorithm in sparse quadratic programming

被引：14

作者：

Arioli, M ^{[1
]}

Baldini, L

机构：

[1] Rutherford Appleton Lab, Didcot OX11 0QX, Oxon, England

[2] Cap Gemini Ernst & Young, I-20123 Milan, Italy

来源：

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS | 2001年 / 23卷 / 02期

关键词：

augmented systems; sparse matrices; Gaussian factorization; roundoff;

D O I：

10.1137/S0895479800375977

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present a roundoff error analysis of a null space method for solving quadratic programming minimization problems. This method combines the use of a direct LU factorization of the constraints with an iterative solver on the corresponding null space. Numerical experiments are presented which give evidence of the good performance of the algorithm on sparse matrices.

引用

页码：425 / 442

页数：18

共 28 条

[1]

ANDERSON Z, 1995, LAPACK USERS GUIDE R

[2] The use of QR factorization in sparse quadratic programming and backward error issues [J].

Arioli, M .

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 2000, 21 (03) :825-839

[3] Stopping criteria for iterative methods: applications to PDE's [J].

Arioli, M ;

Noulard, E ;

Russo, A .

CALCOLO, 2001, 38 (02) :97-112

[4] ITERATIVE METHODS FOR EQUALITY-CONSTRAINED LEAST-SQUARES PROBLEMS [J].

BARLOW, JL ;

NICHOLS, NK ;

PLEMMONS, RJ .

SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1988, 9 (05) :892-906

[5]

CAMPBELL S. L., 1979, Generalized inverses of linear transformations

[6] THE NULL SPACE PROBLEM .1. COMPLEXITY [J].

COLEMAN, TF ;

POTHEN, A .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (04) :527-537

[7] PREDICTING FILL FOR SPARSE ORTHOGONAL FACTORIZATION [J].

COLEMAN, TF ;

EDENBRANDT, A ;

GILBERT, JR .

JOURNAL OF THE ACM, 1986, 33 (03) :517-532

[8] Accuracy and stability of the null space method for solving the equality constrained least squares problem [J].

Cox, AJ ;

Higham, NJ .

BIT NUMERICAL MATHEMATICS, 1999, 39 (01) :34-50

[9] FLOATING-POINT TECHNIQUE FOR EXTENDING AVAILABLE PRECISION [J].

DEKKER, TJ .

NUMERISCHE MATHEMATIK, 1971, 18 (03) :224-+

[10] SPARSE-MATRIX TEST PROBLEMS [J].

DUFF, IS ;

GRIMES, RG ;

LEWIS, JG .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1989, 15 (01) :1-14

← 1 2 3 →