结构线性方程组的迭代方法与扰动分析
|
摘要
论文主要分为两部分，讨论结构化线性方程组的迭代方法和扰动分析。
第一，二章是关于迭代方法的。第一章讨论预条件技术，针对对流扩散问题和Oseen问题离散后系数矩阵所具有的特殊结构，用近似Kronecker积构造预条件子。从而改善系数矩阵的谱性质，加速迭代方法的收敛。第二章讨论非精确的Krylov子空间方法。当外迭代用Krylov子空间方法，内迭代可以用松弛策略，非精确地求解。重点分析了非精确的BiCGStab方法，并提出了相应的松弛策略。讨论了Schur补方程，相关方程用非精确Krylov子空间方法求解时的收敛行为，还提出了与Monte Carlo方法结合的思想。
第三至第五章是关于扰动分析的。第三章讨论鞍点问题的结构化向后误差和条件数，给出了鞍点问题结构化向后误差的一般表达式，并用结构化条件数分析了解的敏感性。第四章用矩阵导数作为工具推导Cauchy矩阵，Vandermonde矩阵等结构化矩阵的混合型和分量型条件数。在第五章我们考察了带Kronecker积的线性系统，得到了与经典结果类似的条件数，并讨论了其二层条件数。
第六章给出了关于子空间距离和奇异值极大极小性质的一个注记。
We discuss the iterative methods and perturbation analysis of structured linear systems in this thesis.
Chapter 1 and Chapter 2 mainly concern about the iterative solution methods. In Chapter 1, we discuss the preconditioning technique. According to the special structure of the coefficient matrix arising from the SUPG discretization of convection-diffusion problem, or the MAC discretization of the Oseen problem, we use Kronecker product approximation to design the preconditioner. So we can change the spectral properties of the coefficient matrix, and improve the convergence. We focus on the inexact Krylov method in Chapter 2. When we use Krylov subspace methods as the outer iteration, we can apply relaxation strategy to inner iteration and use inexact matrix-vector product. We analyze the inexact BiCGStab and provide its corresponding relaxation strategy. We then apply the inexact Krylov subspace method to the Schur complement equation and the related equation. We also propose a new idea of combining relaxation strategy with Monte Carlo method.
We turn to perturbation analysis from Chapter 3 to Chapter 5. In Chapter 3, we discuss the structured backward error and condition numbers of saddle point problem. The explicit general expression of structured backward error is obtained, and the structured condition number is applied to analyze the sensitivity of the solution. In Chapter 4, we use matrix derivative to deduce the mixed and componentwise condition numbers of structured matrix, such as Cauchy matrix, Vandermonde matrix, etc. In Chapter 5, we investigate the linear systems involving Kronecker product. We analyze its condition numbers and the level-2 condition numbers.
In Chapter 6, we give a note on the minimax representation for the subspace distance and singular values.
第一，二章是关于迭代方法的。第一章讨论预条件技术，针对对流扩散问题和Oseen问题离散后系数矩阵所具有的特殊结构，用近似Kronecker积构造预条件子。从而改善系数矩阵的谱性质，加速迭代方法的收敛。第二章讨论非精确的Krylov子空间方法。当外迭代用Krylov子空间方法，内迭代可以用松弛策略，非精确地求解。重点分析了非精确的BiCGStab方法，并提出了相应的松弛策略。讨论了Schur补方程，相关方程用非精确Krylov子空间方法求解时的收敛行为，还提出了与Monte Carlo方法结合的思想。
第三至第五章是关于扰动分析的。第三章讨论鞍点问题的结构化向后误差和条件数，给出了鞍点问题结构化向后误差的一般表达式，并用结构化条件数分析了解的敏感性。第四章用矩阵导数作为工具推导Cauchy矩阵，Vandermonde矩阵等结构化矩阵的混合型和分量型条件数。在第五章我们考察了带Kronecker积的线性系统，得到了与经典结果类似的条件数，并讨论了其二层条件数。
第六章给出了关于子空间距离和奇异值极大极小性质的一个注记。
We discuss the iterative methods and perturbation analysis of structured linear systems in this thesis.
Chapter 1 and Chapter 2 mainly concern about the iterative solution methods. In Chapter 1, we discuss the preconditioning technique. According to the special structure of the coefficient matrix arising from the SUPG discretization of convection-diffusion problem, or the MAC discretization of the Oseen problem, we use Kronecker product approximation to design the preconditioner. So we can change the spectral properties of the coefficient matrix, and improve the convergence. We focus on the inexact Krylov method in Chapter 2. When we use Krylov subspace methods as the outer iteration, we can apply relaxation strategy to inner iteration and use inexact matrix-vector product. We analyze the inexact BiCGStab and provide its corresponding relaxation strategy. We then apply the inexact Krylov subspace method to the Schur complement equation and the related equation. We also propose a new idea of combining relaxation strategy with Monte Carlo method.
We turn to perturbation analysis from Chapter 3 to Chapter 5. In Chapter 3, we discuss the structured backward error and condition numbers of saddle point problem. The explicit general expression of structured backward error is obtained, and the structured condition number is applied to analyze the sensitivity of the solution. In Chapter 4, we use matrix derivative to deduce the mixed and componentwise condition numbers of structured matrix, such as Cauchy matrix, Vandermonde matrix, etc. In Chapter 5, we investigate the linear systems involving Kronecker product. We analyze its condition numbers and the level-2 condition numbers.
In Chapter 6, we give a note on the minimax representation for the subspace distance and singular values.
引文
[1] 曹志浩，多格子方法，复旦大学出版社，1989．
[2] 曹志浩，数值线性代数，复旦大学出版社，1996．
[3] 曹志浩，变分迭代法，科学出版社，2005．
[4] 傅德薰，马延文，计算流体力学，高等教育出版社，2002．
[5] 刘新国，王卫国，关于结构KKT方程组的扰动分析，计算数学，26(2004)，pp．179-188．
[6] 刘新国，王学锋，一类KKT系统的结构敏度分析，计算数学，26(2004)，pp．427-436．
[7] 欧阳光中，流形上的微积分，上海科学技术出版社，1988．
[8] 施恩伟，流形上的微积分，科学出版社，2004．
[9] 施阳，李俊等编著，MATLAB语言工具箱-TOOLBOX实用指南，西北工业大学出版社，1999．
[10] 孙继广，矩阵扰动分析，第二版，科学出版社，2001．
[11] 唐珍，舍入误差分析引论，上海科学技术出版社，1987．
[12] 徐树方，矩阵计算的理论与方法，北京大学出版社，1995．
[13] 徐钟济，蒙特卡罗方法，上海科学技术出版社，1985．
[14] 张涵信，沈孟育，计算流体力学-差分方法的原理和应用，国防工业出版社，2003．
[15] G．H．戈卢布，C．F．范洛恩(著)，袁亚湘等译，矩阵计算，科学出版社，2001．
[16] J．H．威尔金森(著)，石钟慈，邓健新(译)，代数特征值问题，科学出版社，2001．
[17] V. Alexandrov, B. Liu, Hybrid Monte Carlo methods for matrix computation, in Numerical Methods and Applications, I. Dimov et al. (Eds.): NMA 2002, LNCS 2542, pp. 73-82, 2003.
[18] M. Amara, E. Chacon Vera, D. Trujillo, Vorticity-velocity-pressure formulation for Stokes problem, Mathematics of Computation, 73(2003), pp. 1673-1697.
[19] J. D. Anderson, Computational Fluid Dynamics: The Basics with Applications, McGraw-Hill, 1995.
[20] M. Arioli, M. Baboulin, S. Gratton, Partial condition number for linear least squares problems, Technical Report TR/PA/04/111, CERFACS, Toulouse, France.
[21] M. Arioli, L. Baldini, A backward error analysis of a null space algorithm in sparse quadratic programming, SIAM J. Matrix Anal. Appl., 23(2001), pp. 425-442.
[22] W. E. Arnoldi, The principle of minimized iterations in the solution of the matrix eigenvalue problem, Quarterly of Applied Mathematics, 9(1951), pp. 17-29.
[23] O. Axelsson, Iterative Solution Method, Cambridge University Press, 1994.
[24] Z. -Z. Bai, G. H. Golub, M. K. Ng, Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SCCM-01-06, available at http://www-sccm.stanford.edu/pub/sccm/sccm01-06.ps.gz.
[25] Z.-Z. Bai, G. H. Golub, J.-Y. Pan, Preconditioned Hermitian and skewHermitian splitting methods for non-Hermitian positive semidefinite linear systems, available at http://www-sccm.stanford.edu/pub/sccm/sccm02-12.ps.gz.
[26] R. E. Bank, B. D. Welfert, H. Yserentant, A class of iterative methods for solving saddle point problems, Numer. Math., 56(1990), pp. 645-666.
[27] R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, H. A. Van der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadephia, 1994.
[28] S. Barnett, Matrices: Methods and Applications, Oxford University Press, New York, 1990.
[29] A. Barrlund, Efficient solution of constrained least squares problems with Kronecker product structure, SIAM J. Matrix. Anal. Appl., 19(1998), pp. 154-160.
[30] S. G. Bartels, D. J. Higham, The structured sensitivity of Vandermonde-like systems, Numer. Math., 62(1992), pp. 17-33.
[31] M. Bartholomew-Biggs, Nonlinear Optimization with Financial Applications, Kluwer Academic Publisher, 2005.
[32] von F. L. Bauer, Genauigkeitsfragen bei der losung linearer gleichungssysteme, ZAMM, 46(1966), pp. 409-421.
[33] A. Ben-Israel, On error bounds for generalized inverses, SIAM J. Numer. Anal., 4(1966), pp. 585-592.
[34] A. Ben-Israel, T. N. E. Greville, Generalized Inverses: Theory and Applications, 2nd Edition, Springer Verlag, New York, 2003.
[35] M. Benzi, Preconditioning techniques for large linear systems: a survey, J. Comp. Phys., 182(2002), pp. 418-477.
[36] M. Benzi, M. J. Gander, G. H. Golub, Optimization of the Hermitian and skew-Hermitian splitting iteration for saddle-point problems, BIT, 43(2002), pp. 1-13.
[37] M. Benzi, G. H. Golub, An iterative method for generalized saddle point problems, SCCM-02-14, available at http://www-sccm.stanford.edu/pub/sccm/sccm02-14.ps.gz.
[38] M. Benzi, G. H. Golub, A preconditioner for generalized saddle point problems, SIAM J. Matrix Anal. Appl., 26(2004), pp. 20-41.
[39] M. Benzi, G. H. Golub, J. Liesen, Numerical solution of saddle point problems, Acta Numerica, 14(2005), pp. 1-137.
[40] M. Benzi, C. D. Meyer, M. Tuma, A sparse approximate inverse preconditioner for the conjugate gradient method, SIAM J. Sci. Comput., 17(1996), pp. 1135-1149.
[41] M. Benzi, M. Tuma, A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput., 19(1998), pp. 968-994.
[42] M. Benzi, M. Tuma, A comparative study of sparse approximate inverse preconditioners, Appl. Numer. Math., 30(1999), pp. 305-340.
[43] P. Bochev, R. B. Lehoucq, On the finite element solution of the pure Neumann problem, SIAM Rev., 47(2005), pp. 50-66.
[44] M. A. Botchev, G. H. Golub, A class of nonsymmetric preconditioners for saddle point problems, SIAM J. Matrix Anal. Appl., 27(2006), pp. 1125-1149.
[45] A. Bouras, V. Fraysse, Inexact matrix-vector products in Krylov methods for solving linear systems: a relaxation strategy, SIAM J. Matrix Anal. Appl., 26(2005), pp. 660-678.
[46] J. H. Bramble, J. E. Pasciak, A preconditioning technique for indefinite systems resulting from mixed approximations of elliptic problems, Math. Comp., 50(1998), pp. 1-17.
[47] J. H. Bramble, J. E. Pasciak, A. T. Vassilev, Analysis of the inexact Uzawa algorithm for saddle point problems, SIAM J. Numer. Anal., 34(1997), pp. 1072-1092.
[48] J. H. Bramble, J. E. Pasciak, A. T. Vassilev, Uzawa type algorithms for nonsymmetric saddle-point problems, Math. Comp., 69(2000), pp. 667-689.
[49] W. L. Briggs, V. E. Hanson, S. F. McCormick, A Multigrid Tutorial, SIAM, Philadelphia, 2000.
[50] P. N. Brown, H. F. Walker, GMRES on (nearly) singular systems, SIAM J. Matrix Anal. Appl., 18(1997), pp. 37-51.
[51] J. R. Bunch, The weak and strong stability of algorithms in numerical linear algebra, Linear Algebra Appl., 88/89(1987), pp. 49-66.
[52] J. R. Bunch, J. W. Demmel, C. F. Van Loan, The strong stability of algorithms for solving symmetric linear systems, SIAM J. Matrix Anal. Appl., 10(1989), pp. 494-499.
[53] Z. -H. Cao, Avoiding breakdown in variants of the BI-CGSTAB algorithm, Linear Algebra Appl., 263(1997), pp. 113-132.
[54] Z. -H. Cao, A note on constraint preconditioning for nonsymmetric indefinite matrices, SIAM J. Matrix Anal. Appl. 24(2002), pp. 121-125.
[55] Z. -H. Cao, Fast Uzawa algorithm for generalized saddle point problems, Appl. Numer. Math., 46(2003), pp. 157-171.
[56] Z. -H. Cao, Fast Uzawa algorithms for solving non-symmetric stabilized saddle point problems, Numer. Linear Algebra Appl., 11(2004), pp. 1-24.
[57] Z. -H. Cao, Fast iterative solution of stabilized Navier-Stokes systems, Appl. Math. Comput. 157(2004),pp. 219-241.
[58] Z. -H. Cao, Comparison of performance of iterative methods for singular and nonsingular saddle point linear systems arising from Navier-Stokes equations, Appl. Math. Comput., 174(2006), pp. 630-642.
[59] Z. -H. Cao, A class of constraint preconditioners for nonsymmetric saddle point matrices, Numer. Math., 103(2006), pp. 47-61.
[60] Z. -H. Cao, L.-H. Fang, A Note on variational representation for Singular Values of Matrix, Appl. Math. Comp., 143(2003), pp. 559-563.
[61] Z. -H. Cao, Y. -C. Jiang, On algebraic multilevel preconditioning methods, Numer. Math. J. Chinese Univ. (English Set.), 2(1993), pp. 25-37.
[62] T. F. Chan, W. P. Tang, W. L. Wan, Wavelet sparse approximate inverse preconditioners, BIT, 37(1997), pp. 644-660.
[63] F. Chaitin-Chatelin, V. Fraysse, Lectures on Finite Precision Computations, SIAM, Philadelphia, 1996.
[64] K. Chen, Matrix Preconditioning Techniques and Applications, Cambridge University Press, 2005.
[65] B. N. Datta, Numerical Methods for Linear Control Systems, Elsevier Science Press, Amsterdam, 2004.
[66] K. Datta, The matrix equation XA - BX = R and its applications, Linear Algebra and Appl., 109(1988), pp. 91-105.
[67] P. J. Davis, Circulant Matrices, John Wiley & Sons, 1979.
[68] J. W. Demmel, N. J. Higham, Improved error bounds for underdetermined system solvers, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 1-14.
[69] H. Diao, Y. Wei, Structured perturbation of group inverse and singular linear system with index one, J. Comput. Appl. Math., 173(2005), pp. 93-113.
[70] H. Diao, Y. Wei, S. Qiao, Displacement rank of the Drazin inverse, J. Comput. Appl. Math., 167(2004), pp. 147-161.
[71] E. de Sturler, J. Liesen, Block-diagonal and constraint preconditioners for nonsymmetric indefinite linear systems, Part Ⅰ: Theory, SIAM J. Sci. Comput., 26(2005), pp. 1598-1619.
[72] H. S. Dollar, N. I. Gould, A. J. Wathen, On implicit-factorization constraint precondiotioners, Technical report, RAL-TR-2004-036, Rutherford Appleton Laboratory Oxfordshire, England, 2004.
[73] H. S. Dollar, A. J. Wathen, Approximate factorization constraint preconditioners for saddle-point matrices, SIAM J. Sci. Comput., 27(2006), pp. 1555-1572.
[74] J. Dongrra, F. Sullivan, Guest editors' introduction to the top 10 algorithms, Computing in Sciences and Engineering, 2(2000), pp. 22-23.
[75] J. Drkosova, A. Greenbaum, M. Rozloznik and Z. Strakos, Numerical stability of GMRES, BIT, 35(1995), pp. 309-330.
[76] M. Eiermann, O. G. Ernst, Geometric aspects of the theory of Krylov subspace methods, Acta Numerica 2001, pp. 251-312.
[77] H. C. Elman, Iterative methods for linear systems, in Large-Scale Matrix Problems and the Numerical Solution of Partial Differential Equations, Edited by J. Gilbert, D. Kershaw, Advances in Numerical Analysis, Vol. Ⅲ, pp. 69-118, Oxford University Press, 1994.
[78] H. C. Elman, Preconditioning for the steady-state Navier-Stokes equations with low viscosity, SIAM J. Sci. Comput., 20(1999), pp. 1299-1316.
[79] H. C. Elman, Preconditioners for saddle-point problems arising in computational fluid dynamics, Appl. Numer. Math., 43(2002), pp. 75-89.
[80] H. C. Elman, G. H. Golub, Inexact and preconditioned Uzawa algorithms for saddle point problems, SIAM J. Numer. Anal., 31 (1994), pp. 1645-1661.
[81] H. C. Elman, D. Silvester, Fast nonsymmetric iterations and preconditioning for Navier-Stokes equations, SIAM J. Sci. Comput., 17(1996), pp. 33-46.
[82] H. C. Elman, D. J. Silvester, A. J. Wathen, Performance and analysis of saddle point preconditioners for the discrete steady-state Navier-Stokes equations, Numer. Math., 90(2002), pp. 665-688.
[83] H. C. Elman, D. J. Silvester, A. J. Wathen, Finite Elements and Fast Iterative Solvers with Applications in Incompressible Fluid Dynamics, Oxford University Press, New York, 2005.
[84] O. G. Ernst, Residual-minimizing Krylov subspace methods for stabilized discretizations of convection-diffusion equations, SIAM J. Matrix Anal. Appl., 21(2000), pp. 1079-1101.
[85] D. W. Fausett, C. T. Fulton, Large least squares problems involving Kronecker products, SIAM J. Matrix Anal. Appl., 15(1994), pp. 219-227.
[86] D. Fausett, C. Fulton, H. Hashish, Parallel QR method for large least squares problems involving Kronecker products, Internat. J. Appl. Sci. Comput., 2 (1996), pp. 407-421.
[87] D. Fausett, C. Fulton, H. Hashish, Improved parallel QR method for large least squares problems involving Kronecker products, J. Comput. Appl. Math., 78 (1997), pp. 63-78.
[88] J. H. Ferziger, M. Periac, Computational Methods for Fluid Dynamics, Springer-Verlag, New York, 1996.
[89] B. Fischer, A. Ramage, D. Silvester, A. Wathen, On parameter choice and iterative convergence for stabilised discretisations of advection-diffusion problems, Comput. Methods Appl. Mech. Engrg., 179(1999), pp. 179-195.
[90] J. M. Ford, An improved discrete wavelet transform preconditioner for dense matrix problems, SIAM J. Matrix Anal. Appl., 25(2003), pp. 642-661.
[91] J. Ford, K. Chen, Wavelet-based preconditioners for dense matrices with nonsmooth local features, BIT, 41(2001), pp. 282-307.
[92] J. M. Ford, E. E. Tyrtyshnikov, Solving linear systems using wavelet compression combined with Kronecker product approximation, Numerical Algorithms, 40(2005), pp. 125-135.
[93] G. E. Forsythe, Solving linear algebraic equations can be interesting, Bull. Amer. Math. Soc., 59(1953), pp. 299-329.
[94] M. Fortin, Finite element solution of the Navier-Stokes equations, Acta Numerica (1993), pp. 239-284.
[95] R. W. Freund, G. H. Golub, N. M. Nachtigal, Iterative solution of linear systems, Acta Numerica 1992, pp. 57-100.
[96] R. W. Freund, Nachtigal, QMR: a quasi-minimal residual method for nonHermitian linear systems, Numer. Math., 60(1991), pp. 315:339.
[97] C. Fulton, L. Wu, Parallel algorithms for large least squares problems involving Kronecker products, Nonlinear Anal., 30(1997), pp. 5033-5040.
[98] P. Gahinet, A. J. Laub, C. S. Kenney, G. Hewer, Sensitivity of the stable discrete-time Lyapunov equation, IEEE Trans. Auto. Control, 35(1990), pp. 1209-1217.
[99] W. Gautschi, How (un)stable are Vandermonde systems? In Asymptotic and Computational Analysis, R. Wong, editor, Vol. 124 of Lecture Notes in Pure and Applied Mathematics, Marcel Dekker, New York and Basel, 1990.
[100] A. J. Geurts, A Contribution to the theory of condition, Numer. Math., 39(1982), pp. 85-90.
[101] A. Ghavimi, A. Laub, Backward error, sensivity and refinement of computed solutions of algebraic Riccati equations. Numer. Lin. Alg. Appl., 2(1995), pp. 29-49.
[102] L. Giraud, S. Gratton, J. Langou, Convergence in backward error of relazed GMRES, Technical Report TR/PA/06/08, CERFACS, Toulouse, France, 2006, available at http://www.cerfacs.fr/algor/reports/2006/TR_ PA_ 06_ 08. pdf.
[103] J. W. Givens, Numerical computation of the characteristic values of a real symmetric matrix, Rep. ORNL-1574, Oak Ridge Natl. Lab., Oak Ridge, Tenn., 1954.
[104] R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer Series in Computational Physics, Springer-Verlag, New York, 1984.
[105] I. Gohberg, I. Koltracht, On the Inversion of Cauchy Matrices, Proceedings of the International Symposium MTNS-89, Vol. Ⅲ, Birkhauser, 1990, pp. 381-293.
[106] I. Gohberg, I. Koltracht, Mixed, componentwise, and structured condition numbers, SIAM J. Matrix Anal. Appl., 14(1993), pp. 688-704.
[107] I. Gohberg, I. Koltracht, Structured condition numbers for linear matrix structures, In Linear Algebra for Singal Processing, A. Bojunczyk and G. Cybenko, eds., IMA Vol. Math. Appl. 69, Springer-Verlog, New York, 1995, pp. 17-26.
[108] H. H. Goldstine, A History of Numerical Analysis from the 16th through the 19th century, Springer-Verlag, 1977, pp. 258-260.
[109] G. H. Golub, C. Greif, On solving block-structured indefinite linear systems, SIAM J. Sci. Comput., 24(2003), pp. 2076-2092.
[110] G. H. Golub, C. Greif, J. M. Varah, An algebraic analysis of a block diagonal preconditioner for saddle point systems, available at http://www-sccm.stanford.edu/pub/sccm/sccm05-04.pdf.
[111] G. H. Golub, S. Nash, C. F. Van Loan, A Hessenberg-Schur methods for the problem AX + XB = C, IEEE Trans. Auto. Control, Vol. AC-24(1979), No. 6, pp. 909-913.
[112] G. H. Golub, D. P. O'Leary, Some history of the conjugate gradient and Lanczos methods: 1948-1976, SIAM Rev., 31(1989), pp. 50-102.
[113] G. H. Golub, C. F. Van Loan, Matrix Computations, 3rd Edition, John Hopkins University Press, Baltimore, MD, 1996.
[114] G. H. Golub, A. J. Wathen, An iteration for indefinite systems and its application to the Navier-Stokes equations, SIAM J. Sci. Comput., 19(1998), pp. 530-539.
[115] G. H. Golub, X. Wu, J. -Y. Yuan, SOR-like methods for augmented systems, BIT, 41(2001), pp. 71-85.
[116] N. I. M. Gould, M. E. Hribar, J. Nocedal, On the solution of equality constrained quadratic programming problems arising in optimization, SIAM J. Sci. Comput., 23(2001), pp. 1376-1395.
[117] N. I. M. Gould, J. A. Scott, Sparse approximate-inverse preconditioners using norm-minimization techniques, SIAM J. Sci. Comput., 19(1998), pp. 605-625.
[118] A. Graham, Kronecker Products and Matrix Calculus with Application, Wiley, New York, 1981.
[119] S. Gratton, On the condition number of linear least squares problems in a weighted Frobenius norm, BIT, 36(1996), pp. 523-530.
[120] A. Greenbaum, Iterative Methods for solving Linear Systems, SIAM, Philadelphia, 1997.
[121] A. Greenbaum, V. Ptak, Z. Strakos, Any nonincrease convergence curve is possible for GMRES, SIAM J. Matrix Anal. Appl., 17(1996), pp. 465-469.
[122] C. Greif, G. H. Golub, J. M. Varah, Augmented Lagrangian techniques for solving saddle point linear systems, available at http://www-sccm.stanford.edu/pub/sccm/sccm04-08.pdf.
[123] P. M. Gresho, R. L. Saul, Incompressible Flow and the Finite Element Method, Volume 2: Isothermal Laminar Flow, John Wiley & Sons Ltd, 1998.
[124] M. Grote, T. Huckle, Parallel preconditioning with sparse approximate inverse, SIAM J. Sci. Comput., 18(1997), pp. 838-853.
[125] M. Gulliksson, X. Jin, Y. Wei, Perturbation bounds for constrained and weighted least squares problems, Linear Algebra Appl., 349(2002), pp. 221-232.
[126] M. Gulliksson, P. Wedin, Perturbation theory for generalized and constrained linear least squares, Numer. Linear Algebra Appl., 7(2000), pp. 181-195.
[127] M. H. Gutknecht, A brief introduction to Krylov space methods for solving linear systems, available at http://www.sam.math.ethz.ch/ mhg/pub/biksm.pdf.
[128] W. Hackbush, Iterative Solution of Large Sparse Systems of Equations, Springer-Verlag New York, Inc., 1994.
[129] A. L. Hageman, D. M. Young, Applied Iterative Methods, Academic Press, New York, 1981.
[130] F. J. Hall, Generalized inverses of a bordered matrix of operators, SIAM J. Appl. Math., 1(1975), pp. 152-163.
[131] J. M. Hammersley, D. C. Handscomb, Monte Carlo Methods, John Wiley & Sons Inc., New York, 1964.
[132] F. H. Harlow, J. E. Welsh, Numerical calculation of time dependent viscous incompressible flow with free surface, Phys. Fluid, 8(1965), pp. 2182-2189.
[133] S. C. Hawkins, K. Chen, An implicit wavelet sparse approximate inverse preconditioner, SIAM J. Sci. Comput., 27(2005), pp. 667-686.
[134] J. Z. Hearon, Nonsingular solution ofTA- BT = C, Linear Algebra Appl., 16(1977), pp. 57-63.
[135] G. Heinig, Inversion of generalized Cauchy matrices and other classes of structured matrices, in Linear Algebra for Singal Processing, Springer Verlag, 1995, pp. 63-81.
[136] H. V. Henderson, S. R. Searle, The vec-permutation matrix, the vec operator and Kronecker products: A review, Linear and Multilinear Algebra, 9(1981), pp. 271-288.
[137] M. R. Hestenes, E. Stiefel, Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards, 49(1952), pp. 409-436.
[138] G. Hewer, C. Kenney, The sensitivity of the stable Lyapunov equation, SIAM J. Control Opt., 26(1988), pp. 321-344.
[139] D. J. Higham, Condition numbers and their condition numbers, Linear Algebra Appl., 214(1995), pp. 193-213.
[140] D. J. Higham, N. J. Higham, MATLAB Guide, SIAM, Philadelphia, 2000.
[141] D. J. Higham, N. J. Higham, Componentwise perturbation theory for linear systems with multiple right-hand sides, Linear Algebra Appl., 174(1992), pp. 111-129.
[142] D. J. Higham, N. J. Higham, Backward error and condition of structured linear systems, SIAM J. Matrix Anal. Appl., 13(1992), pp. 162-175.
[143] N. J. Higham, Perturbation theory and backward error for AX - XB = C, BIT, 33(1993), pp. 124-136.
[144] N. J. Higham, A survey of componentwise perturbation theory in numerical linear algebra, Proceedings of Symposia in Applied Mathematics, Vol.48, 1994, pp. 49-77.
[145] N. J. Higham, Accuracy and stability of Numerical Algorithms, 2nd Edition, SIAM, Philadelphia, 2002.
[146] R. A. Horn, C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, Cambridge, 1991.
[147] H. Hotelling, Some new methods in matrix calculation, Ann. Math. Statistics, 14(1943), pp. 1-34.
[148] A. S. Householder, A class of methods for inverting matrices, J. Soc. Indust. Appl. Math., 6(1958), pp. 189-195.
[149] W. Huyer, A. Neumaier, Global optimization by multilevel coordinate search, J. Global Optimization, 14(1999), pp. 331-355.
[150] I. C. F. Ipsen, C. D. Meyer, The angle between complementary subspaces, Amer. Math. Monthly, 102(1995), pp. 904-911.
[151] X. Jin, Developments and Applications of Block Toeplitz Iterative Solvers, Kluwer Academic Publishers Dordrecht and Science Press, Beijing, 2002.
[152] X. Jin, Y. Wei, Numerical Linear Algebra and its Applications, Science Press, Beijing / New York, 2004.
[153] B. Kagstrom, A perturbation analysis of the generalized Sylvester equation (AR - LB, DR - LE) = (C, F), SIAM J. Matrix Anal. Appl., 15(1994), pp. 1045-1060.
[154] W. Kahan, Numerical linear algebra, Canad. Math. Bull., 9(1966), pp. 757-801.
[155] C. Keller, N. I. M. Gould, A. J. Wathen, Constraint preconditioning for indefinite linear systems, SIAM J. Matrix Anal. Appl., 21(2000), pp.1300-1317.
[156] C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations, SIAM, Philadelphia, 1995.
[157] C. S. Kenney, A. J. Laub, M. S. Reese, Statistical conditon estimation for linear systems, SIAM J. Sci. Comput., 19(1998), pp. 566-583.
[158] A. Klawonn, Block-triangular preconditioners for saddle point problems with a penalty term, SIAM J. Sci. Comput., 19(1998), pp. 172-184.
[159] A. Klawonn, An optimal preconditioner for a class of saddle point problems with a penalty term, SIAM J. Sci. Comput., 19(1998), pp. 540-552.
[160] A. Klawonn, G. Starke, Block triangular preconditioners for nonsymmetric saddle point problems: field-of-value analysis, Numer. Math., 81(1999), pp. 577-594.
[161] L. Yu Kolotilina, A. Yu Yeremin, Factorized sparse approximate inverse preconditionings, SIAM J. Matrix Anal. Appl., 14(1993), pp. 45-58.
[162] M. Konstantinov, D. Gu, V. Mehrmann, P. Petkov, Perturbation Theory for Matrix Equations, Elsevier Science Press, Amsterdam, 2003.
[163] M. Konstantinov, V. Mehrmann, P. Petkov, On the properties of general Sylvester and Lyapunov operators, Linear Algebra Appl., 312(2000), pp. 35-71.
[164] M. Konstantinov, P. Petkov, D. W. Gu, V. Mehrmann, Sensitivity of general Lyapunov equations, Technical Report 98-15, Dept. of Engineering, Leicester Univ., Leicester, UK, 1993.
[165] B. V. R. Kumar, M. Mehra, Wavelet based preconditioners for sparse linear systems, Appl. Math. Comput., 171(2005), pp. 203-224.
[166] P. Lancaster, Explicit solution of linear matrix equations, SIAM Rev., 12(1970), pp. 544-566.
[167] P. Lancaster, M. Tismenetsky, The Theory of Matrices, 2nd Edition, Academic Press, Orlando, FL, 1985.
[168] C. Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, Journal of Research of the National Bureau of Standards, 45(1950), pp. 255-282.
[169] C. Lanczos, Solution of systems of linear equations by minimized iterations, Journal of Research of the National Bureau of Standards, 49(1952), pp. 33-53.
[170] A. N. Langville, W. J. Stewart, A Kronecker product approximate preconditioner for SANs, Numer. Lin. Algebra Appl., 11(2004), pp. 723-752.
[171] A. N. Langville, W. J. Stewart, Testing the Nearest Kronecker Product Preconditioner on Markov Chains and Stochastic Automata Networks, INFORMS J. Computing, 16(2004), pp. 300-315.
[172] A. N. Langville, W. J. Stewart, The Kronecker product and stochastic automata networks, J. Comput. Appl. Math., 167(2004), pp.429-447.
[173] S. Lesecq, A. Barraud, N. Christov, On the local Sensitivity of the Lyapunov equations, in NAA 2000, LNCS 1988, L. Vulkov, J. Wasniewski, and P. Yalamov(Eds.), pp. 521-526, 2001.
[174] X. S. Li, J. W. Demmel, SuperLU_ DIST: A scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM Trans. Math. Software, 29(2003), pp. 110-140.
[175] X. Li, X. Liu, Structured backward errors for structured KKT systems, J. Comp. Math., 22(2004), pp. 605-610.
[176] J. Liesen, Z. Strakos, GMRES convergence analysis for a convectiondiffusion model problem, SIAM J. Sci. Comput., 26(2005), pp. 1989-2009.
[177] H. Lomax, T. H. Pulliam, D. W. Zingg, Fundamentals of Computational Fluid Dynamics, Springer, 2001.
[178] J. R. Magnus, H. Neudecker, Matrix Differential Calculus with Applications in Statistics and Econometrics, John Wiley & Sons, 1988.
[179] J. A. Meijerink, H. A. van der Vorst, An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix, Math. Comp., 31(1977), pp. 148-162.
[180] C. D. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM, Philadelphia, 2000.
[181] C. B. Moler, Numerical Computing with MATLAB, SIAM, Philadelphia, 2004.
[182] K. W. Morton, Numerical Solution of Convection-Diffusion Problems, Chapman & Hall, London, 1996.
[183] M. F. Murphy, G. H. Golub, A. J. Wathen, A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comput. 21(2000), pp. 1969-1972.
[184] J. Nagy, M. K. Ng, L. Perrone, Kronecker product approximations for image restoration with reflexive boundary conditions, SIAM J. Matrix Anal. Appl., 25 (2003), pp. 829-841.
[185] J. Nocedal, S. Wright, Numerical Optimization, Springer-Verlag, New York, 1999.
[186] W. Oettli, W. Prager, Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides, Numer. Math., 6(1964), pp. 405-409.
[187] G. Okten, Solving linear equations by Monte Carlo simulation, SIAM J. Sci. Comput., 27(2005), pp. 511-531.
[188] M. A. Olshanskii, An iterative solver for the Oseen problem and numerical solution of incompressible Navier-Stokes equations, Numer. Linear Algebra Appl., 6(1999), pp. 353-378.
[189] M. A. Olshanskii, A. Reusken, Navier-Stokes equations in rotation form: A robust multigrid solver for the velocity problem, SIAM J. Sci. Comput., 23(2002), pp. 1683-1706.
[190] C. C. Page, M. A. Sauders, Solution of sparse indefinite systems of linear equations. SIAM J. Numr. Anal., 12(1975), pp. 617-629.
[191] C. C. Paige, M. Rozloznik, Z. Strakos, Modified Gram-Schmidt (MGS), least squares, and backward stability of MGS-GMRES, SIAM J. Matrix Anal. Appl., to appear.
[192] N. Pitsianis, C. F. Van Loan, Approximation with Kronecker products, in Linear Algebra for Large Scale and Real Time Applications, M. S. Moonen, G. H. Golub (eds), Kluwer Academics, Boston, 1993, pp. 293-314.
[193] A. Quarteroni, F. Saleri, Scientific Computing with MATLAB, Springer, New York, 2003.
[194] A. Quarteroni, A. Valli, Numerical Approximation of Partial Differential Equations, Springer Ser. Comput. Math. 23, Springer-Verlag, Berlin, 1994.
[195] J. R. Rice, A theory of condition, SIAM J. Numer. Anal., 3(1966), pp. 287-310.
[196] J. L. Rigal, J. Gaches, On the compatibility of a given solution with data of a linear system, J. Assoc. Comput. Mach., 14(1967), pp. 543-548.
[197] S. C. Reddy, L. N. Trefethen, Pseudospectra of the convection-diffusion operator, SIAM J. Appl. Math., 54(1994), pp. 1634-1649.
[198] J. K. Reid, On the method of conjugate directions for the solution of large sparse systems of equations, in John K. Reid, editor, Large Sparse Sets of Linear Equations, pp. 231-254, Academic Press, New York, 1971.
[199] G. S. Rogers, Matrix Derivatives, Marcel Dekker Inc., 1980.
[200] J. Rohn, New condition numbers for matrices and linear systems, Computing, 41(1989), pp. 167-169.
[201] H. -G. Roos, M. Stynes, L. Tobiska, Numerical Methods for Singularly Perturbed Differential Equations, Springer Set. Comput. Math. 24, SpringerVerlag, Berlin, 1996.
[202] M. Rozloznik, V. Simoncini, Krylov subspace methods for saddle point problems with indefinite preconditioning, SIAM J. Matrix Anal. Appl., 24(2004), pp. 368-391.
[203] R. Rump, Optimal scaling for p-norms and componetwise distance to singularity, IMA J. Numerical Analysis, 23(2003), pp. 1-9.
[204] S. M. Rump, Structured perturbations Part Ⅰ: normwise distances, SIAM J. Matrix Anal. Appl., 25(2003), pp. 1-30.
[205] S. M. Rump, Structured perturbations Part Ⅱ: componentwise distances, SIAM J. Matrix Anal. Appl., 25(2003), pp. 31-56.
[206] T. Rusten, R. Winther, A preconditioned iterative method for saddlepoint problems, SIAM J. Matrix Anal. Appl., 13(1992), pp. 887-904.
[207] Y. Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Stat. Comput., 14(1993), pp. 461-469.
[208] Y. Saad, Iterative Methods for Sparse Linear Systems, Second Edition, SIAM, Philadelphia, 2003.
[209] Y. Saad, M. H. Schultz, GMRES: a generalized minmal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput., 7(1986), pp. 856-869.
[210] Y. Saad, H. A. van der Vorst, Iterative solution of linear systems in the 20th century, J. Comput. Appl. Math., 123(2000), pp. 1-33.
[211] V. Sarin, A. Sameh, An efficient iterative method for the generalized Stokes problem, SIAM J. Sci. Comput., 19(1998), pp. 206-226.
[212] A. Sidi, A zero-cost preconditioning for a class of indefinite linear systems, WSEAS Transactions on Mathematics, 2(2003), pp. 142-150.
[213] D. J. Silvester, H. C. Elman, D. Kay, A. J. Wathen, Efficient preconditioning of the linearized Navier-Stokes equations for incompressible flow, J. Comput. Appl. Math., 128(2001), pp. 261-279.
[214] V. Simoncini, Variable accuracy of matrix-vector products in projection methods for eigencomputation, SIAM J. Numer. Anal., 43(2005), pp. 1155-1174.
[215] V. Simoncini, D. B. Szyld, Theory of inexact Krylov subspace methods and applications to scientific computing, SIAM J. Sci. Comput., 25(2003), pp. 454-477.
[216] V. Simoncini, D. B. Szyld, Flexible inner-outer Krylov subspace methods, SIAM J. Numer. Anal., 40(2003), pp. 2219-2239.
[217] V. Simoncini, D. B. Szyld, Recent Developments in Krylov Subspace Methods for linear systems, to appear in Numer. Linear Algebra Appl., available at http://www.math.temple.edu/~szyld/reports/survey_report.pdf.
[218] V. Simoncini, D. B. Szyld, On the occurrence of superlinear convergence of exact and inexact Krylov subspace methods, SIAM Rev., 47(2005), pp. 247-272.
[219] R. D. Skeel, Scaling for numerical stability in Gaussian elimination, J. Assoc. Comput. Mach., 26(1979), pp. 494-526.
[220] G. D. Smith, Numerical Solution of Partial Differential Eequations: Finite Difference Methods, Oxford University Press, 1978.
[221] A. Smoktunowicz, A note on the strong componentwise stability of algorithms for solving symmetric linear systems, Demonstratio Mathematica, 28(1995), pp. 443-448 (cited by Higham).
[222] I. M. Sobol, The Monte Carlo Method, English translation, Mir Publishers, 1975.
[223] P. Sonneveld, CGS: a fast Lanczos-type solver for nonsymmetric linear systems. SIAM J. Sci. Statist. Comput., 10(1989), pp. 36-52.
[224] G. Starke, W. Niethammer, SOR for AX - XB = C, Linear Algebra Appl., 154-156(1991), pp. 355-375.
[225] G. W. Stewart, J.-G. Sun, Matrix Perturbation Theory, Academic Press, New York, 1990.
[226] G. Strang, Wavelets and dilation equations: a brief introduction, SIAM Rev., 31(1989), pp. 613-627.
[227] J. C. Strikwerda, Finite Difference Schemes and Partial Differential Equations, SIAM, Philadelphia, 2004.
[228] K. Stuben, Algebraic multigrid(AMG): experiences and comparison, Appl. Math. Comput., 13(1983), pp. 419.
[229] K. Stuben, A review of algebraic multigrid, J. Comput. Appl. Math., 128(2001), pp.281-309.
[230] J. -G. Sun, Backward perturbation analysis of certain characteristic subspaces, Numer. Math., 65(1993), pp. 357-382.
[231] J. -G. Sun, Bounds for the structured backward errors for Vandermonde systems, SIAM J. Matrix Anal. Appl., 20(1998), pp. 45-59.
[232] J.-G. Sun, Structured backward errors for KKT systems, Linear Algebra Appl., 288(1999), pp. 75-88.
[233] J.-G. Sun, Condition numbers of algebraic Riccati equations in the Frobenius norm, Linear Algebra Appl., 350(2002), pp. 237-261.
[234] J. -G. Sun, A note on backward errors for structured linear systems, Numer. Linear Algebra Appl., 12(2005), pp. 585 - 603.
[235] J. -G. Sun, Z. Sun, Optimal backward perturbation bounds for underdetermined systems, SIAM J. Matrix Anal. Appl., 18(1997), pp. 393-402.
[236] D. B. Szyld, J. A. Vogel, FQMR: A flexible quasi-minimal residual method with inexact preconditioning, SIAM J. Sci. Comput., 23(2001), pp. 363-380.
[237] J. Todd, The condition of certain matrices, I, Quart. J. Mech. Appl. Math., 2(1949), pp. 464-472.
[238] L. N. Trefethen, Pseudospectra of linear operators, SIAM Rev., 39(1997), pp. 383-406.
[239] L. N. Trefethen, D. Bau Ⅲ, Numerical Linear Algebra, SIAM, Philadelphia, 1997.
[240] A. M. Turing, Rounding-off errors in matrix processes, The Quarterly J. Mech. Appl. Math., 3(1948), pp. 287-308.
[241] K. Urban, Wavelets in Numerical Simulation: Problem Adapted Construction and Applications, Springer, 2002.
[242] H. A. van der Vorst, Bi-CGSTAB: A fast and smoothing converging variant of Bi-CG for solution of non-symmetric linear systems. SIAM J. Sci. Statist. Comput., 13(1992), pp. 631-644.
[243] H. A. van der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge Monographs on Applied and Computationl Mathematics, Cambridge University Press, Cambridge, UK, 2003.
[244] J. van den Eshof, G. Sleijpen, M. B. van Gijzen, Iterative linear system solvers with approximate matrix-vector products, Technical Report TR/PA/04/133, CERFACS, Toulouse, France, 2004, available at http://www.cerfacs.fr/algor/reports/2004/TR_ PA_ 04_ 133.pdf.
[245] J. van den Eshof, G. Sleijpen, M. B. van Gijzen, Relaxation strategies for nested Krylov methods, Technical Report TR/PA/03/27, CERFACS, Toulouse, France, 2003, available at http://www.math.uu.nl/publications/preprints/1268.pdf.
[246] J. van den Eshof, G. Sleijpen, Inexact Krylov subspace methods for linear systems, SIAM J. Matrix Anal. Appl., 26(2004), pp. 125-153.
[247] C. F. Van Loan, The ubiquitous Kronecker product, J. Comput. Appl. Math., 123(2000), pp. 85-100.
[248] J. M. Varah, Backward error estimates for Toeplitz systems, SIAM J. Matrix Anal. Appl., 15(1994), pp. 408-417.
[249] R. S. Varga, Matrix Iterative Analysis, Prentice-Hall, Englewood Cliffs, NJ, 1962.
[250] S. A. Vavasis, Stable numerical algorithms for equilibrium systems, SIAM J. Matrix Anal. Appl., 15(1994), pp. 1108-1131.
[251] J. von Neumann, H. H. Goldstine, Numerical inverting of matrices of high order, Bull. Amer. Math. Soc., 53(1947), pp. 1021-1047, see also Proc. Amer. Math. Soc., 2(1951), pp. 188-202.
[252] G. Wang, Y. Wei, S. Qiao, Generalized Inverses: Theory and Computations, Science Press, Beijing, 2004.
[253] Y. Wei, Y. Cao, H. Xiang, A note on the componentwise perturbation bounds of matrix inverse and linear systems, Appl. Math. Comput., 169(2005), pp. 1221-1236.
[254] Y. Wei, D. Wang, Condition numbers and perturbation of the weighted Moore-Penrose inverse and weighted linear least squares problem, Appl. Math. Comput., 145(2003), pp. 45-58.
[255] Y. Wei, H. Diao, S. Qiao, Condition number for weighted linear least squares problem and its condition number, Technical Report No. CAS 04-02-SQ, De- partment of Computing and Software, McMaster University, Hamilton, Ontario, Canada. LSS 4K1. May 2004.
[256] P. Wesseling, Principles of Computational Fluid Dynamics, Springer, 2001.
[257] J. H. Wilkinson, Error analysis of floating-point computation, Numer. Math., 2(1960), pp. 319-340.
[258] J. H. Wilkinson, Error analysis of direct methods of matrix inversion, Journal of the Association of Computing Machinery, 8(1961), pp. 281-330.
[259] J. H. Wilkinson, Rounding Errors in Algebra Process, Prentice-Hall, Englewood Cliffs, New Jersey, 1963.
[260] J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford Univ. Press (Clarendon), London and New York, 1965.
[261] J. H. Wilkinson, Modern error ananysis, SIAM Rev., 13(1971), pp. 548-568.
[262] H. Xiang, A note on minimax representation for subspace distance and singular values, Linear Algebra Appl., 414(2006), pp. 470-473.
[263] H. Xiang, H. Diao, Y. Wei, On the perturbation bounds of Kronecker product linear systems and their level-2 condition numbers, J. Comput. Appl. Math., 183(2005), pp. 210-231.
[264] H. Xiang, H. Diao, Y. Wei, Normwise, mixed and componentwise condition numbers of Moore-Penrose inverse and linear least squares problem, submitted to Linear Algebra and its Application.
[265] H. Xiang, H. Diao, Y. Wei, New condition numbers of Sylvester and Lyapunov equations, in preparation.
[266] H. Xiang, Y. Wei, Structured mixed and componentwise condition numbers of some structured matrices, J. Comput. Appl. Math., 2006 (in press).
[267] H. Xiang, Y. Wei, On the normwise structured backward errors for KKT systems, submitted to Numerische Mathematik.
[268] H. Xiang, Y. Wei, H. Diao, Perturbation analysis of generalized saddle point systems, Linear Algebra Appl., 2006 (in press).
[269] D. M. Young, Iterative Methods for Solving Partial Difference Equations of Elliptic Type, PhD thesis, Harvard University, 1950, available at http://www-sccm.stanford.edu/pub/sccm/david_young_thesis.ps.gz.
[270] D. M. Young, Iterative Solution of Large Linear Systems, Academic Press, New York, 1971.
[271] Jens-Peter M. Zemke, Krylov Subspace Methods in Finite Precision: A Unified Approach, PhD Thesis, 2003.
[272] H. Zha, Comments on large least squares problems involving Kronecker products, SIAM J. Matrix Anal. Appl., 16(1995), pp. 1172.
[273] N. Zhang, Y. Wei, Solving EP singular linear systems, Int. J. Comput. Math., 81(2004), pp. 1395-1405.
[274] N. Zhang, Y. Wei, A note on solving EP inconsistent linear systems, Appl. Math. Comput., 169(2005), pp. 8-15.
[275] W. Zulenher, Analysis of iterative methods for saddle point problems: A unified approach, Math. Comp., 71(2002), pp. 479-505.
[2] 曹志浩，数值线性代数，复旦大学出版社，1996．
[3] 曹志浩，变分迭代法，科学出版社，2005．
[4] 傅德薰，马延文，计算流体力学，高等教育出版社，2002．
[5] 刘新国，王卫国，关于结构KKT方程组的扰动分析，计算数学，26(2004)，pp．179-188．
[6] 刘新国，王学锋，一类KKT系统的结构敏度分析，计算数学，26(2004)，pp．427-436．
[7] 欧阳光中，流形上的微积分，上海科学技术出版社，1988．
[8] 施恩伟，流形上的微积分，科学出版社，2004．
[9] 施阳，李俊等编著，MATLAB语言工具箱-TOOLBOX实用指南，西北工业大学出版社，1999．
[10] 孙继广，矩阵扰动分析，第二版，科学出版社，2001．
[11] 唐珍，舍入误差分析引论，上海科学技术出版社，1987．
[12] 徐树方，矩阵计算的理论与方法，北京大学出版社，1995．
[13] 徐钟济，蒙特卡罗方法，上海科学技术出版社，1985．
[14] 张涵信，沈孟育，计算流体力学-差分方法的原理和应用，国防工业出版社，2003．
[15] G．H．戈卢布，C．F．范洛恩(著)，袁亚湘等译，矩阵计算，科学出版社，2001．
[16] J．H．威尔金森(著)，石钟慈，邓健新(译)，代数特征值问题，科学出版社，2001．
[17] V. Alexandrov, B. Liu, Hybrid Monte Carlo methods for matrix computation, in Numerical Methods and Applications, I. Dimov et al. (Eds.): NMA 2002, LNCS 2542, pp. 73-82, 2003.
[18] M. Amara, E. Chacon Vera, D. Trujillo, Vorticity-velocity-pressure formulation for Stokes problem, Mathematics of Computation, 73(2003), pp. 1673-1697.
[19] J. D. Anderson, Computational Fluid Dynamics: The Basics with Applications, McGraw-Hill, 1995.
[20] M. Arioli, M. Baboulin, S. Gratton, Partial condition number for linear least squares problems, Technical Report TR/PA/04/111, CERFACS, Toulouse, France.
[21] M. Arioli, L. Baldini, A backward error analysis of a null space algorithm in sparse quadratic programming, SIAM J. Matrix Anal. Appl., 23(2001), pp. 425-442.
[22] W. E. Arnoldi, The principle of minimized iterations in the solution of the matrix eigenvalue problem, Quarterly of Applied Mathematics, 9(1951), pp. 17-29.
[23] O. Axelsson, Iterative Solution Method, Cambridge University Press, 1994.
[24] Z. -Z. Bai, G. H. Golub, M. K. Ng, Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SCCM-01-06, available at http://www-sccm.stanford.edu/pub/sccm/sccm01-06.ps.gz.
[25] Z.-Z. Bai, G. H. Golub, J.-Y. Pan, Preconditioned Hermitian and skewHermitian splitting methods for non-Hermitian positive semidefinite linear systems, available at http://www-sccm.stanford.edu/pub/sccm/sccm02-12.ps.gz.
[26] R. E. Bank, B. D. Welfert, H. Yserentant, A class of iterative methods for solving saddle point problems, Numer. Math., 56(1990), pp. 645-666.
[27] R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, H. A. Van der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadephia, 1994.
[28] S. Barnett, Matrices: Methods and Applications, Oxford University Press, New York, 1990.
[29] A. Barrlund, Efficient solution of constrained least squares problems with Kronecker product structure, SIAM J. Matrix. Anal. Appl., 19(1998), pp. 154-160.
[30] S. G. Bartels, D. J. Higham, The structured sensitivity of Vandermonde-like systems, Numer. Math., 62(1992), pp. 17-33.
[31] M. Bartholomew-Biggs, Nonlinear Optimization with Financial Applications, Kluwer Academic Publisher, 2005.
[32] von F. L. Bauer, Genauigkeitsfragen bei der losung linearer gleichungssysteme, ZAMM, 46(1966), pp. 409-421.
[33] A. Ben-Israel, On error bounds for generalized inverses, SIAM J. Numer. Anal., 4(1966), pp. 585-592.
[34] A. Ben-Israel, T. N. E. Greville, Generalized Inverses: Theory and Applications, 2nd Edition, Springer Verlag, New York, 2003.
[35] M. Benzi, Preconditioning techniques for large linear systems: a survey, J. Comp. Phys., 182(2002), pp. 418-477.
[36] M. Benzi, M. J. Gander, G. H. Golub, Optimization of the Hermitian and skew-Hermitian splitting iteration for saddle-point problems, BIT, 43(2002), pp. 1-13.
[37] M. Benzi, G. H. Golub, An iterative method for generalized saddle point problems, SCCM-02-14, available at http://www-sccm.stanford.edu/pub/sccm/sccm02-14.ps.gz.
[38] M. Benzi, G. H. Golub, A preconditioner for generalized saddle point problems, SIAM J. Matrix Anal. Appl., 26(2004), pp. 20-41.
[39] M. Benzi, G. H. Golub, J. Liesen, Numerical solution of saddle point problems, Acta Numerica, 14(2005), pp. 1-137.
[40] M. Benzi, C. D. Meyer, M. Tuma, A sparse approximate inverse preconditioner for the conjugate gradient method, SIAM J. Sci. Comput., 17(1996), pp. 1135-1149.
[41] M. Benzi, M. Tuma, A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput., 19(1998), pp. 968-994.
[42] M. Benzi, M. Tuma, A comparative study of sparse approximate inverse preconditioners, Appl. Numer. Math., 30(1999), pp. 305-340.
[43] P. Bochev, R. B. Lehoucq, On the finite element solution of the pure Neumann problem, SIAM Rev., 47(2005), pp. 50-66.
[44] M. A. Botchev, G. H. Golub, A class of nonsymmetric preconditioners for saddle point problems, SIAM J. Matrix Anal. Appl., 27(2006), pp. 1125-1149.
[45] A. Bouras, V. Fraysse, Inexact matrix-vector products in Krylov methods for solving linear systems: a relaxation strategy, SIAM J. Matrix Anal. Appl., 26(2005), pp. 660-678.
[46] J. H. Bramble, J. E. Pasciak, A preconditioning technique for indefinite systems resulting from mixed approximations of elliptic problems, Math. Comp., 50(1998), pp. 1-17.
[47] J. H. Bramble, J. E. Pasciak, A. T. Vassilev, Analysis of the inexact Uzawa algorithm for saddle point problems, SIAM J. Numer. Anal., 34(1997), pp. 1072-1092.
[48] J. H. Bramble, J. E. Pasciak, A. T. Vassilev, Uzawa type algorithms for nonsymmetric saddle-point problems, Math. Comp., 69(2000), pp. 667-689.
[49] W. L. Briggs, V. E. Hanson, S. F. McCormick, A Multigrid Tutorial, SIAM, Philadelphia, 2000.
[50] P. N. Brown, H. F. Walker, GMRES on (nearly) singular systems, SIAM J. Matrix Anal. Appl., 18(1997), pp. 37-51.
[51] J. R. Bunch, The weak and strong stability of algorithms in numerical linear algebra, Linear Algebra Appl., 88/89(1987), pp. 49-66.
[52] J. R. Bunch, J. W. Demmel, C. F. Van Loan, The strong stability of algorithms for solving symmetric linear systems, SIAM J. Matrix Anal. Appl., 10(1989), pp. 494-499.
[53] Z. -H. Cao, Avoiding breakdown in variants of the BI-CGSTAB algorithm, Linear Algebra Appl., 263(1997), pp. 113-132.
[54] Z. -H. Cao, A note on constraint preconditioning for nonsymmetric indefinite matrices, SIAM J. Matrix Anal. Appl. 24(2002), pp. 121-125.
[55] Z. -H. Cao, Fast Uzawa algorithm for generalized saddle point problems, Appl. Numer. Math., 46(2003), pp. 157-171.
[56] Z. -H. Cao, Fast Uzawa algorithms for solving non-symmetric stabilized saddle point problems, Numer. Linear Algebra Appl., 11(2004), pp. 1-24.
[57] Z. -H. Cao, Fast iterative solution of stabilized Navier-Stokes systems, Appl. Math. Comput. 157(2004),pp. 219-241.
[58] Z. -H. Cao, Comparison of performance of iterative methods for singular and nonsingular saddle point linear systems arising from Navier-Stokes equations, Appl. Math. Comput., 174(2006), pp. 630-642.
[59] Z. -H. Cao, A class of constraint preconditioners for nonsymmetric saddle point matrices, Numer. Math., 103(2006), pp. 47-61.
[60] Z. -H. Cao, L.-H. Fang, A Note on variational representation for Singular Values of Matrix, Appl. Math. Comp., 143(2003), pp. 559-563.
[61] Z. -H. Cao, Y. -C. Jiang, On algebraic multilevel preconditioning methods, Numer. Math. J. Chinese Univ. (English Set.), 2(1993), pp. 25-37.
[62] T. F. Chan, W. P. Tang, W. L. Wan, Wavelet sparse approximate inverse preconditioners, BIT, 37(1997), pp. 644-660.
[63] F. Chaitin-Chatelin, V. Fraysse, Lectures on Finite Precision Computations, SIAM, Philadelphia, 1996.
[64] K. Chen, Matrix Preconditioning Techniques and Applications, Cambridge University Press, 2005.
[65] B. N. Datta, Numerical Methods for Linear Control Systems, Elsevier Science Press, Amsterdam, 2004.
[66] K. Datta, The matrix equation XA - BX = R and its applications, Linear Algebra and Appl., 109(1988), pp. 91-105.
[67] P. J. Davis, Circulant Matrices, John Wiley & Sons, 1979.
[68] J. W. Demmel, N. J. Higham, Improved error bounds for underdetermined system solvers, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 1-14.
[69] H. Diao, Y. Wei, Structured perturbation of group inverse and singular linear system with index one, J. Comput. Appl. Math., 173(2005), pp. 93-113.
[70] H. Diao, Y. Wei, S. Qiao, Displacement rank of the Drazin inverse, J. Comput. Appl. Math., 167(2004), pp. 147-161.
[71] E. de Sturler, J. Liesen, Block-diagonal and constraint preconditioners for nonsymmetric indefinite linear systems, Part Ⅰ: Theory, SIAM J. Sci. Comput., 26(2005), pp. 1598-1619.
[72] H. S. Dollar, N. I. Gould, A. J. Wathen, On implicit-factorization constraint precondiotioners, Technical report, RAL-TR-2004-036, Rutherford Appleton Laboratory Oxfordshire, England, 2004.
[73] H. S. Dollar, A. J. Wathen, Approximate factorization constraint preconditioners for saddle-point matrices, SIAM J. Sci. Comput., 27(2006), pp. 1555-1572.
[74] J. Dongrra, F. Sullivan, Guest editors' introduction to the top 10 algorithms, Computing in Sciences and Engineering, 2(2000), pp. 22-23.
[75] J. Drkosova, A. Greenbaum, M. Rozloznik and Z. Strakos, Numerical stability of GMRES, BIT, 35(1995), pp. 309-330.
[76] M. Eiermann, O. G. Ernst, Geometric aspects of the theory of Krylov subspace methods, Acta Numerica 2001, pp. 251-312.
[77] H. C. Elman, Iterative methods for linear systems, in Large-Scale Matrix Problems and the Numerical Solution of Partial Differential Equations, Edited by J. Gilbert, D. Kershaw, Advances in Numerical Analysis, Vol. Ⅲ, pp. 69-118, Oxford University Press, 1994.
[78] H. C. Elman, Preconditioning for the steady-state Navier-Stokes equations with low viscosity, SIAM J. Sci. Comput., 20(1999), pp. 1299-1316.
[79] H. C. Elman, Preconditioners for saddle-point problems arising in computational fluid dynamics, Appl. Numer. Math., 43(2002), pp. 75-89.
[80] H. C. Elman, G. H. Golub, Inexact and preconditioned Uzawa algorithms for saddle point problems, SIAM J. Numer. Anal., 31 (1994), pp. 1645-1661.
[81] H. C. Elman, D. Silvester, Fast nonsymmetric iterations and preconditioning for Navier-Stokes equations, SIAM J. Sci. Comput., 17(1996), pp. 33-46.
[82] H. C. Elman, D. J. Silvester, A. J. Wathen, Performance and analysis of saddle point preconditioners for the discrete steady-state Navier-Stokes equations, Numer. Math., 90(2002), pp. 665-688.
[83] H. C. Elman, D. J. Silvester, A. J. Wathen, Finite Elements and Fast Iterative Solvers with Applications in Incompressible Fluid Dynamics, Oxford University Press, New York, 2005.
[84] O. G. Ernst, Residual-minimizing Krylov subspace methods for stabilized discretizations of convection-diffusion equations, SIAM J. Matrix Anal. Appl., 21(2000), pp. 1079-1101.
[85] D. W. Fausett, C. T. Fulton, Large least squares problems involving Kronecker products, SIAM J. Matrix Anal. Appl., 15(1994), pp. 219-227.
[86] D. Fausett, C. Fulton, H. Hashish, Parallel QR method for large least squares problems involving Kronecker products, Internat. J. Appl. Sci. Comput., 2 (1996), pp. 407-421.
[87] D. Fausett, C. Fulton, H. Hashish, Improved parallel QR method for large least squares problems involving Kronecker products, J. Comput. Appl. Math., 78 (1997), pp. 63-78.
[88] J. H. Ferziger, M. Periac, Computational Methods for Fluid Dynamics, Springer-Verlag, New York, 1996.
[89] B. Fischer, A. Ramage, D. Silvester, A. Wathen, On parameter choice and iterative convergence for stabilised discretisations of advection-diffusion problems, Comput. Methods Appl. Mech. Engrg., 179(1999), pp. 179-195.
[90] J. M. Ford, An improved discrete wavelet transform preconditioner for dense matrix problems, SIAM J. Matrix Anal. Appl., 25(2003), pp. 642-661.
[91] J. Ford, K. Chen, Wavelet-based preconditioners for dense matrices with nonsmooth local features, BIT, 41(2001), pp. 282-307.
[92] J. M. Ford, E. E. Tyrtyshnikov, Solving linear systems using wavelet compression combined with Kronecker product approximation, Numerical Algorithms, 40(2005), pp. 125-135.
[93] G. E. Forsythe, Solving linear algebraic equations can be interesting, Bull. Amer. Math. Soc., 59(1953), pp. 299-329.
[94] M. Fortin, Finite element solution of the Navier-Stokes equations, Acta Numerica (1993), pp. 239-284.
[95] R. W. Freund, G. H. Golub, N. M. Nachtigal, Iterative solution of linear systems, Acta Numerica 1992, pp. 57-100.
[96] R. W. Freund, Nachtigal, QMR: a quasi-minimal residual method for nonHermitian linear systems, Numer. Math., 60(1991), pp. 315:339.
[97] C. Fulton, L. Wu, Parallel algorithms for large least squares problems involving Kronecker products, Nonlinear Anal., 30(1997), pp. 5033-5040.
[98] P. Gahinet, A. J. Laub, C. S. Kenney, G. Hewer, Sensitivity of the stable discrete-time Lyapunov equation, IEEE Trans. Auto. Control, 35(1990), pp. 1209-1217.
[99] W. Gautschi, How (un)stable are Vandermonde systems? In Asymptotic and Computational Analysis, R. Wong, editor, Vol. 124 of Lecture Notes in Pure and Applied Mathematics, Marcel Dekker, New York and Basel, 1990.
[100] A. J. Geurts, A Contribution to the theory of condition, Numer. Math., 39(1982), pp. 85-90.
[101] A. Ghavimi, A. Laub, Backward error, sensivity and refinement of computed solutions of algebraic Riccati equations. Numer. Lin. Alg. Appl., 2(1995), pp. 29-49.
[102] L. Giraud, S. Gratton, J. Langou, Convergence in backward error of relazed GMRES, Technical Report TR/PA/06/08, CERFACS, Toulouse, France, 2006, available at http://www.cerfacs.fr/algor/reports/2006/TR_ PA_ 06_ 08. pdf.
[103] J. W. Givens, Numerical computation of the characteristic values of a real symmetric matrix, Rep. ORNL-1574, Oak Ridge Natl. Lab., Oak Ridge, Tenn., 1954.
[104] R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer Series in Computational Physics, Springer-Verlag, New York, 1984.
[105] I. Gohberg, I. Koltracht, On the Inversion of Cauchy Matrices, Proceedings of the International Symposium MTNS-89, Vol. Ⅲ, Birkhauser, 1990, pp. 381-293.
[106] I. Gohberg, I. Koltracht, Mixed, componentwise, and structured condition numbers, SIAM J. Matrix Anal. Appl., 14(1993), pp. 688-704.
[107] I. Gohberg, I. Koltracht, Structured condition numbers for linear matrix structures, In Linear Algebra for Singal Processing, A. Bojunczyk and G. Cybenko, eds., IMA Vol. Math. Appl. 69, Springer-Verlog, New York, 1995, pp. 17-26.
[108] H. H. Goldstine, A History of Numerical Analysis from the 16th through the 19th century, Springer-Verlag, 1977, pp. 258-260.
[109] G. H. Golub, C. Greif, On solving block-structured indefinite linear systems, SIAM J. Sci. Comput., 24(2003), pp. 2076-2092.
[110] G. H. Golub, C. Greif, J. M. Varah, An algebraic analysis of a block diagonal preconditioner for saddle point systems, available at http://www-sccm.stanford.edu/pub/sccm/sccm05-04.pdf.
[111] G. H. Golub, S. Nash, C. F. Van Loan, A Hessenberg-Schur methods for the problem AX + XB = C, IEEE Trans. Auto. Control, Vol. AC-24(1979), No. 6, pp. 909-913.
[112] G. H. Golub, D. P. O'Leary, Some history of the conjugate gradient and Lanczos methods: 1948-1976, SIAM Rev., 31(1989), pp. 50-102.
[113] G. H. Golub, C. F. Van Loan, Matrix Computations, 3rd Edition, John Hopkins University Press, Baltimore, MD, 1996.
[114] G. H. Golub, A. J. Wathen, An iteration for indefinite systems and its application to the Navier-Stokes equations, SIAM J. Sci. Comput., 19(1998), pp. 530-539.
[115] G. H. Golub, X. Wu, J. -Y. Yuan, SOR-like methods for augmented systems, BIT, 41(2001), pp. 71-85.
[116] N. I. M. Gould, M. E. Hribar, J. Nocedal, On the solution of equality constrained quadratic programming problems arising in optimization, SIAM J. Sci. Comput., 23(2001), pp. 1376-1395.
[117] N. I. M. Gould, J. A. Scott, Sparse approximate-inverse preconditioners using norm-minimization techniques, SIAM J. Sci. Comput., 19(1998), pp. 605-625.
[118] A. Graham, Kronecker Products and Matrix Calculus with Application, Wiley, New York, 1981.
[119] S. Gratton, On the condition number of linear least squares problems in a weighted Frobenius norm, BIT, 36(1996), pp. 523-530.
[120] A. Greenbaum, Iterative Methods for solving Linear Systems, SIAM, Philadelphia, 1997.
[121] A. Greenbaum, V. Ptak, Z. Strakos, Any nonincrease convergence curve is possible for GMRES, SIAM J. Matrix Anal. Appl., 17(1996), pp. 465-469.
[122] C. Greif, G. H. Golub, J. M. Varah, Augmented Lagrangian techniques for solving saddle point linear systems, available at http://www-sccm.stanford.edu/pub/sccm/sccm04-08.pdf.
[123] P. M. Gresho, R. L. Saul, Incompressible Flow and the Finite Element Method, Volume 2: Isothermal Laminar Flow, John Wiley & Sons Ltd, 1998.
[124] M. Grote, T. Huckle, Parallel preconditioning with sparse approximate inverse, SIAM J. Sci. Comput., 18(1997), pp. 838-853.
[125] M. Gulliksson, X. Jin, Y. Wei, Perturbation bounds for constrained and weighted least squares problems, Linear Algebra Appl., 349(2002), pp. 221-232.
[126] M. Gulliksson, P. Wedin, Perturbation theory for generalized and constrained linear least squares, Numer. Linear Algebra Appl., 7(2000), pp. 181-195.
[127] M. H. Gutknecht, A brief introduction to Krylov space methods for solving linear systems, available at http://www.sam.math.ethz.ch/ mhg/pub/biksm.pdf.
[128] W. Hackbush, Iterative Solution of Large Sparse Systems of Equations, Springer-Verlag New York, Inc., 1994.
[129] A. L. Hageman, D. M. Young, Applied Iterative Methods, Academic Press, New York, 1981.
[130] F. J. Hall, Generalized inverses of a bordered matrix of operators, SIAM J. Appl. Math., 1(1975), pp. 152-163.
[131] J. M. Hammersley, D. C. Handscomb, Monte Carlo Methods, John Wiley & Sons Inc., New York, 1964.
[132] F. H. Harlow, J. E. Welsh, Numerical calculation of time dependent viscous incompressible flow with free surface, Phys. Fluid, 8(1965), pp. 2182-2189.
[133] S. C. Hawkins, K. Chen, An implicit wavelet sparse approximate inverse preconditioner, SIAM J. Sci. Comput., 27(2005), pp. 667-686.
[134] J. Z. Hearon, Nonsingular solution ofTA- BT = C, Linear Algebra Appl., 16(1977), pp. 57-63.
[135] G. Heinig, Inversion of generalized Cauchy matrices and other classes of structured matrices, in Linear Algebra for Singal Processing, Springer Verlag, 1995, pp. 63-81.
[136] H. V. Henderson, S. R. Searle, The vec-permutation matrix, the vec operator and Kronecker products: A review, Linear and Multilinear Algebra, 9(1981), pp. 271-288.
[137] M. R. Hestenes, E. Stiefel, Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards, 49(1952), pp. 409-436.
[138] G. Hewer, C. Kenney, The sensitivity of the stable Lyapunov equation, SIAM J. Control Opt., 26(1988), pp. 321-344.
[139] D. J. Higham, Condition numbers and their condition numbers, Linear Algebra Appl., 214(1995), pp. 193-213.
[140] D. J. Higham, N. J. Higham, MATLAB Guide, SIAM, Philadelphia, 2000.
[141] D. J. Higham, N. J. Higham, Componentwise perturbation theory for linear systems with multiple right-hand sides, Linear Algebra Appl., 174(1992), pp. 111-129.
[142] D. J. Higham, N. J. Higham, Backward error and condition of structured linear systems, SIAM J. Matrix Anal. Appl., 13(1992), pp. 162-175.
[143] N. J. Higham, Perturbation theory and backward error for AX - XB = C, BIT, 33(1993), pp. 124-136.
[144] N. J. Higham, A survey of componentwise perturbation theory in numerical linear algebra, Proceedings of Symposia in Applied Mathematics, Vol.48, 1994, pp. 49-77.
[145] N. J. Higham, Accuracy and stability of Numerical Algorithms, 2nd Edition, SIAM, Philadelphia, 2002.
[146] R. A. Horn, C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, Cambridge, 1991.
[147] H. Hotelling, Some new methods in matrix calculation, Ann. Math. Statistics, 14(1943), pp. 1-34.
[148] A. S. Householder, A class of methods for inverting matrices, J. Soc. Indust. Appl. Math., 6(1958), pp. 189-195.
[149] W. Huyer, A. Neumaier, Global optimization by multilevel coordinate search, J. Global Optimization, 14(1999), pp. 331-355.
[150] I. C. F. Ipsen, C. D. Meyer, The angle between complementary subspaces, Amer. Math. Monthly, 102(1995), pp. 904-911.
[151] X. Jin, Developments and Applications of Block Toeplitz Iterative Solvers, Kluwer Academic Publishers Dordrecht and Science Press, Beijing, 2002.
[152] X. Jin, Y. Wei, Numerical Linear Algebra and its Applications, Science Press, Beijing / New York, 2004.
[153] B. Kagstrom, A perturbation analysis of the generalized Sylvester equation (AR - LB, DR - LE) = (C, F), SIAM J. Matrix Anal. Appl., 15(1994), pp. 1045-1060.
[154] W. Kahan, Numerical linear algebra, Canad. Math. Bull., 9(1966), pp. 757-801.
[155] C. Keller, N. I. M. Gould, A. J. Wathen, Constraint preconditioning for indefinite linear systems, SIAM J. Matrix Anal. Appl., 21(2000), pp.1300-1317.
[156] C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations, SIAM, Philadelphia, 1995.
[157] C. S. Kenney, A. J. Laub, M. S. Reese, Statistical conditon estimation for linear systems, SIAM J. Sci. Comput., 19(1998), pp. 566-583.
[158] A. Klawonn, Block-triangular preconditioners for saddle point problems with a penalty term, SIAM J. Sci. Comput., 19(1998), pp. 172-184.
[159] A. Klawonn, An optimal preconditioner for a class of saddle point problems with a penalty term, SIAM J. Sci. Comput., 19(1998), pp. 540-552.
[160] A. Klawonn, G. Starke, Block triangular preconditioners for nonsymmetric saddle point problems: field-of-value analysis, Numer. Math., 81(1999), pp. 577-594.
[161] L. Yu Kolotilina, A. Yu Yeremin, Factorized sparse approximate inverse preconditionings, SIAM J. Matrix Anal. Appl., 14(1993), pp. 45-58.
[162] M. Konstantinov, D. Gu, V. Mehrmann, P. Petkov, Perturbation Theory for Matrix Equations, Elsevier Science Press, Amsterdam, 2003.
[163] M. Konstantinov, V. Mehrmann, P. Petkov, On the properties of general Sylvester and Lyapunov operators, Linear Algebra Appl., 312(2000), pp. 35-71.
[164] M. Konstantinov, P. Petkov, D. W. Gu, V. Mehrmann, Sensitivity of general Lyapunov equations, Technical Report 98-15, Dept. of Engineering, Leicester Univ., Leicester, UK, 1993.
[165] B. V. R. Kumar, M. Mehra, Wavelet based preconditioners for sparse linear systems, Appl. Math. Comput., 171(2005), pp. 203-224.
[166] P. Lancaster, Explicit solution of linear matrix equations, SIAM Rev., 12(1970), pp. 544-566.
[167] P. Lancaster, M. Tismenetsky, The Theory of Matrices, 2nd Edition, Academic Press, Orlando, FL, 1985.
[168] C. Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, Journal of Research of the National Bureau of Standards, 45(1950), pp. 255-282.
[169] C. Lanczos, Solution of systems of linear equations by minimized iterations, Journal of Research of the National Bureau of Standards, 49(1952), pp. 33-53.
[170] A. N. Langville, W. J. Stewart, A Kronecker product approximate preconditioner for SANs, Numer. Lin. Algebra Appl., 11(2004), pp. 723-752.
[171] A. N. Langville, W. J. Stewart, Testing the Nearest Kronecker Product Preconditioner on Markov Chains and Stochastic Automata Networks, INFORMS J. Computing, 16(2004), pp. 300-315.
[172] A. N. Langville, W. J. Stewart, The Kronecker product and stochastic automata networks, J. Comput. Appl. Math., 167(2004), pp.429-447.
[173] S. Lesecq, A. Barraud, N. Christov, On the local Sensitivity of the Lyapunov equations, in NAA 2000, LNCS 1988, L. Vulkov, J. Wasniewski, and P. Yalamov(Eds.), pp. 521-526, 2001.
[174] X. S. Li, J. W. Demmel, SuperLU_ DIST: A scalable distributed-memory sparse direct solver for unsymmetric linear systems, ACM Trans. Math. Software, 29(2003), pp. 110-140.
[175] X. Li, X. Liu, Structured backward errors for structured KKT systems, J. Comp. Math., 22(2004), pp. 605-610.
[176] J. Liesen, Z. Strakos, GMRES convergence analysis for a convectiondiffusion model problem, SIAM J. Sci. Comput., 26(2005), pp. 1989-2009.
[177] H. Lomax, T. H. Pulliam, D. W. Zingg, Fundamentals of Computational Fluid Dynamics, Springer, 2001.
[178] J. R. Magnus, H. Neudecker, Matrix Differential Calculus with Applications in Statistics and Econometrics, John Wiley & Sons, 1988.
[179] J. A. Meijerink, H. A. van der Vorst, An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix, Math. Comp., 31(1977), pp. 148-162.
[180] C. D. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM, Philadelphia, 2000.
[181] C. B. Moler, Numerical Computing with MATLAB, SIAM, Philadelphia, 2004.
[182] K. W. Morton, Numerical Solution of Convection-Diffusion Problems, Chapman & Hall, London, 1996.
[183] M. F. Murphy, G. H. Golub, A. J. Wathen, A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comput. 21(2000), pp. 1969-1972.
[184] J. Nagy, M. K. Ng, L. Perrone, Kronecker product approximations for image restoration with reflexive boundary conditions, SIAM J. Matrix Anal. Appl., 25 (2003), pp. 829-841.
[185] J. Nocedal, S. Wright, Numerical Optimization, Springer-Verlag, New York, 1999.
[186] W. Oettli, W. Prager, Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides, Numer. Math., 6(1964), pp. 405-409.
[187] G. Okten, Solving linear equations by Monte Carlo simulation, SIAM J. Sci. Comput., 27(2005), pp. 511-531.
[188] M. A. Olshanskii, An iterative solver for the Oseen problem and numerical solution of incompressible Navier-Stokes equations, Numer. Linear Algebra Appl., 6(1999), pp. 353-378.
[189] M. A. Olshanskii, A. Reusken, Navier-Stokes equations in rotation form: A robust multigrid solver for the velocity problem, SIAM J. Sci. Comput., 23(2002), pp. 1683-1706.
[190] C. C. Page, M. A. Sauders, Solution of sparse indefinite systems of linear equations. SIAM J. Numr. Anal., 12(1975), pp. 617-629.
[191] C. C. Paige, M. Rozloznik, Z. Strakos, Modified Gram-Schmidt (MGS), least squares, and backward stability of MGS-GMRES, SIAM J. Matrix Anal. Appl., to appear.
[192] N. Pitsianis, C. F. Van Loan, Approximation with Kronecker products, in Linear Algebra for Large Scale and Real Time Applications, M. S. Moonen, G. H. Golub (eds), Kluwer Academics, Boston, 1993, pp. 293-314.
[193] A. Quarteroni, F. Saleri, Scientific Computing with MATLAB, Springer, New York, 2003.
[194] A. Quarteroni, A. Valli, Numerical Approximation of Partial Differential Equations, Springer Ser. Comput. Math. 23, Springer-Verlag, Berlin, 1994.
[195] J. R. Rice, A theory of condition, SIAM J. Numer. Anal., 3(1966), pp. 287-310.
[196] J. L. Rigal, J. Gaches, On the compatibility of a given solution with data of a linear system, J. Assoc. Comput. Mach., 14(1967), pp. 543-548.
[197] S. C. Reddy, L. N. Trefethen, Pseudospectra of the convection-diffusion operator, SIAM J. Appl. Math., 54(1994), pp. 1634-1649.
[198] J. K. Reid, On the method of conjugate directions for the solution of large sparse systems of equations, in John K. Reid, editor, Large Sparse Sets of Linear Equations, pp. 231-254, Academic Press, New York, 1971.
[199] G. S. Rogers, Matrix Derivatives, Marcel Dekker Inc., 1980.
[200] J. Rohn, New condition numbers for matrices and linear systems, Computing, 41(1989), pp. 167-169.
[201] H. -G. Roos, M. Stynes, L. Tobiska, Numerical Methods for Singularly Perturbed Differential Equations, Springer Set. Comput. Math. 24, SpringerVerlag, Berlin, 1996.
[202] M. Rozloznik, V. Simoncini, Krylov subspace methods for saddle point problems with indefinite preconditioning, SIAM J. Matrix Anal. Appl., 24(2004), pp. 368-391.
[203] R. Rump, Optimal scaling for p-norms and componetwise distance to singularity, IMA J. Numerical Analysis, 23(2003), pp. 1-9.
[204] S. M. Rump, Structured perturbations Part Ⅰ: normwise distances, SIAM J. Matrix Anal. Appl., 25(2003), pp. 1-30.
[205] S. M. Rump, Structured perturbations Part Ⅱ: componentwise distances, SIAM J. Matrix Anal. Appl., 25(2003), pp. 31-56.
[206] T. Rusten, R. Winther, A preconditioned iterative method for saddlepoint problems, SIAM J. Matrix Anal. Appl., 13(1992), pp. 887-904.
[207] Y. Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Stat. Comput., 14(1993), pp. 461-469.
[208] Y. Saad, Iterative Methods for Sparse Linear Systems, Second Edition, SIAM, Philadelphia, 2003.
[209] Y. Saad, M. H. Schultz, GMRES: a generalized minmal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput., 7(1986), pp. 856-869.
[210] Y. Saad, H. A. van der Vorst, Iterative solution of linear systems in the 20th century, J. Comput. Appl. Math., 123(2000), pp. 1-33.
[211] V. Sarin, A. Sameh, An efficient iterative method for the generalized Stokes problem, SIAM J. Sci. Comput., 19(1998), pp. 206-226.
[212] A. Sidi, A zero-cost preconditioning for a class of indefinite linear systems, WSEAS Transactions on Mathematics, 2(2003), pp. 142-150.
[213] D. J. Silvester, H. C. Elman, D. Kay, A. J. Wathen, Efficient preconditioning of the linearized Navier-Stokes equations for incompressible flow, J. Comput. Appl. Math., 128(2001), pp. 261-279.
[214] V. Simoncini, Variable accuracy of matrix-vector products in projection methods for eigencomputation, SIAM J. Numer. Anal., 43(2005), pp. 1155-1174.
[215] V. Simoncini, D. B. Szyld, Theory of inexact Krylov subspace methods and applications to scientific computing, SIAM J. Sci. Comput., 25(2003), pp. 454-477.
[216] V. Simoncini, D. B. Szyld, Flexible inner-outer Krylov subspace methods, SIAM J. Numer. Anal., 40(2003), pp. 2219-2239.
[217] V. Simoncini, D. B. Szyld, Recent Developments in Krylov Subspace Methods for linear systems, to appear in Numer. Linear Algebra Appl., available at http://www.math.temple.edu/~szyld/reports/survey_report.pdf.
[218] V. Simoncini, D. B. Szyld, On the occurrence of superlinear convergence of exact and inexact Krylov subspace methods, SIAM Rev., 47(2005), pp. 247-272.
[219] R. D. Skeel, Scaling for numerical stability in Gaussian elimination, J. Assoc. Comput. Mach., 26(1979), pp. 494-526.
[220] G. D. Smith, Numerical Solution of Partial Differential Eequations: Finite Difference Methods, Oxford University Press, 1978.
[221] A. Smoktunowicz, A note on the strong componentwise stability of algorithms for solving symmetric linear systems, Demonstratio Mathematica, 28(1995), pp. 443-448 (cited by Higham).
[222] I. M. Sobol, The Monte Carlo Method, English translation, Mir Publishers, 1975.
[223] P. Sonneveld, CGS: a fast Lanczos-type solver for nonsymmetric linear systems. SIAM J. Sci. Statist. Comput., 10(1989), pp. 36-52.
[224] G. Starke, W. Niethammer, SOR for AX - XB = C, Linear Algebra Appl., 154-156(1991), pp. 355-375.
[225] G. W. Stewart, J.-G. Sun, Matrix Perturbation Theory, Academic Press, New York, 1990.
[226] G. Strang, Wavelets and dilation equations: a brief introduction, SIAM Rev., 31(1989), pp. 613-627.
[227] J. C. Strikwerda, Finite Difference Schemes and Partial Differential Equations, SIAM, Philadelphia, 2004.
[228] K. Stuben, Algebraic multigrid(AMG): experiences and comparison, Appl. Math. Comput., 13(1983), pp. 419.
[229] K. Stuben, A review of algebraic multigrid, J. Comput. Appl. Math., 128(2001), pp.281-309.
[230] J. -G. Sun, Backward perturbation analysis of certain characteristic subspaces, Numer. Math., 65(1993), pp. 357-382.
[231] J. -G. Sun, Bounds for the structured backward errors for Vandermonde systems, SIAM J. Matrix Anal. Appl., 20(1998), pp. 45-59.
[232] J.-G. Sun, Structured backward errors for KKT systems, Linear Algebra Appl., 288(1999), pp. 75-88.
[233] J.-G. Sun, Condition numbers of algebraic Riccati equations in the Frobenius norm, Linear Algebra Appl., 350(2002), pp. 237-261.
[234] J. -G. Sun, A note on backward errors for structured linear systems, Numer. Linear Algebra Appl., 12(2005), pp. 585 - 603.
[235] J. -G. Sun, Z. Sun, Optimal backward perturbation bounds for underdetermined systems, SIAM J. Matrix Anal. Appl., 18(1997), pp. 393-402.
[236] D. B. Szyld, J. A. Vogel, FQMR: A flexible quasi-minimal residual method with inexact preconditioning, SIAM J. Sci. Comput., 23(2001), pp. 363-380.
[237] J. Todd, The condition of certain matrices, I, Quart. J. Mech. Appl. Math., 2(1949), pp. 464-472.
[238] L. N. Trefethen, Pseudospectra of linear operators, SIAM Rev., 39(1997), pp. 383-406.
[239] L. N. Trefethen, D. Bau Ⅲ, Numerical Linear Algebra, SIAM, Philadelphia, 1997.
[240] A. M. Turing, Rounding-off errors in matrix processes, The Quarterly J. Mech. Appl. Math., 3(1948), pp. 287-308.
[241] K. Urban, Wavelets in Numerical Simulation: Problem Adapted Construction and Applications, Springer, 2002.
[242] H. A. van der Vorst, Bi-CGSTAB: A fast and smoothing converging variant of Bi-CG for solution of non-symmetric linear systems. SIAM J. Sci. Statist. Comput., 13(1992), pp. 631-644.
[243] H. A. van der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge Monographs on Applied and Computationl Mathematics, Cambridge University Press, Cambridge, UK, 2003.
[244] J. van den Eshof, G. Sleijpen, M. B. van Gijzen, Iterative linear system solvers with approximate matrix-vector products, Technical Report TR/PA/04/133, CERFACS, Toulouse, France, 2004, available at http://www.cerfacs.fr/algor/reports/2004/TR_ PA_ 04_ 133.pdf.
[245] J. van den Eshof, G. Sleijpen, M. B. van Gijzen, Relaxation strategies for nested Krylov methods, Technical Report TR/PA/03/27, CERFACS, Toulouse, France, 2003, available at http://www.math.uu.nl/publications/preprints/1268.pdf.
[246] J. van den Eshof, G. Sleijpen, Inexact Krylov subspace methods for linear systems, SIAM J. Matrix Anal. Appl., 26(2004), pp. 125-153.
[247] C. F. Van Loan, The ubiquitous Kronecker product, J. Comput. Appl. Math., 123(2000), pp. 85-100.
[248] J. M. Varah, Backward error estimates for Toeplitz systems, SIAM J. Matrix Anal. Appl., 15(1994), pp. 408-417.
[249] R. S. Varga, Matrix Iterative Analysis, Prentice-Hall, Englewood Cliffs, NJ, 1962.
[250] S. A. Vavasis, Stable numerical algorithms for equilibrium systems, SIAM J. Matrix Anal. Appl., 15(1994), pp. 1108-1131.
[251] J. von Neumann, H. H. Goldstine, Numerical inverting of matrices of high order, Bull. Amer. Math. Soc., 53(1947), pp. 1021-1047, see also Proc. Amer. Math. Soc., 2(1951), pp. 188-202.
[252] G. Wang, Y. Wei, S. Qiao, Generalized Inverses: Theory and Computations, Science Press, Beijing, 2004.
[253] Y. Wei, Y. Cao, H. Xiang, A note on the componentwise perturbation bounds of matrix inverse and linear systems, Appl. Math. Comput., 169(2005), pp. 1221-1236.
[254] Y. Wei, D. Wang, Condition numbers and perturbation of the weighted Moore-Penrose inverse and weighted linear least squares problem, Appl. Math. Comput., 145(2003), pp. 45-58.
[255] Y. Wei, H. Diao, S. Qiao, Condition number for weighted linear least squares problem and its condition number, Technical Report No. CAS 04-02-SQ, De- partment of Computing and Software, McMaster University, Hamilton, Ontario, Canada. LSS 4K1. May 2004.
[256] P. Wesseling, Principles of Computational Fluid Dynamics, Springer, 2001.
[257] J. H. Wilkinson, Error analysis of floating-point computation, Numer. Math., 2(1960), pp. 319-340.
[258] J. H. Wilkinson, Error analysis of direct methods of matrix inversion, Journal of the Association of Computing Machinery, 8(1961), pp. 281-330.
[259] J. H. Wilkinson, Rounding Errors in Algebra Process, Prentice-Hall, Englewood Cliffs, New Jersey, 1963.
[260] J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford Univ. Press (Clarendon), London and New York, 1965.
[261] J. H. Wilkinson, Modern error ananysis, SIAM Rev., 13(1971), pp. 548-568.
[262] H. Xiang, A note on minimax representation for subspace distance and singular values, Linear Algebra Appl., 414(2006), pp. 470-473.
[263] H. Xiang, H. Diao, Y. Wei, On the perturbation bounds of Kronecker product linear systems and their level-2 condition numbers, J. Comput. Appl. Math., 183(2005), pp. 210-231.
[264] H. Xiang, H. Diao, Y. Wei, Normwise, mixed and componentwise condition numbers of Moore-Penrose inverse and linear least squares problem, submitted to Linear Algebra and its Application.
[265] H. Xiang, H. Diao, Y. Wei, New condition numbers of Sylvester and Lyapunov equations, in preparation.
[266] H. Xiang, Y. Wei, Structured mixed and componentwise condition numbers of some structured matrices, J. Comput. Appl. Math., 2006 (in press).
[267] H. Xiang, Y. Wei, On the normwise structured backward errors for KKT systems, submitted to Numerische Mathematik.
[268] H. Xiang, Y. Wei, H. Diao, Perturbation analysis of generalized saddle point systems, Linear Algebra Appl., 2006 (in press).
[269] D. M. Young, Iterative Methods for Solving Partial Difference Equations of Elliptic Type, PhD thesis, Harvard University, 1950, available at http://www-sccm.stanford.edu/pub/sccm/david_young_thesis.ps.gz.
[270] D. M. Young, Iterative Solution of Large Linear Systems, Academic Press, New York, 1971.
[271] Jens-Peter M. Zemke, Krylov Subspace Methods in Finite Precision: A Unified Approach, PhD Thesis, 2003.
[272] H. Zha, Comments on large least squares problems involving Kronecker products, SIAM J. Matrix Anal. Appl., 16(1995), pp. 1172.
[273] N. Zhang, Y. Wei, Solving EP singular linear systems, Int. J. Comput. Math., 81(2004), pp. 1395-1405.
[274] N. Zhang, Y. Wei, A note on solving EP inconsistent linear systems, Appl. Math. Comput., 169(2005), pp. 8-15.
[275] W. Zulenher, Analysis of iterative methods for saddle point problems: A unified approach, Math. Comp., 71(2002), pp. 479-505.