共查询到20条相似文献,搜索用时 31 毫秒
1.
Hongyuan Zha 《BIT Numerical Mathematics》1991,31(4):711-726
A new decomposition of a matrix triplet (A, B, C) corresponding to the singular value decomposition of the matrix productABC is developed in this paper, which will be termed theProduct-Product Singular Value Decomposition (PPSVD). An orthogonal variant of the decomposition which is more suitable for the purpose of numerical computation is also proposed. Some geometric and algebraic issues of the PPSVD, such as the variational and geometric interpretations, and uniqueness properties are discussed. A numerical algorithm for stably computing the PPSVD is given based on the implicit Kogbetliantz technique. A numerical example is outlined to demonstrate the accuracy of the proposed algorithm.The work was partially supported by NSF grant DCR-8412314. 相似文献
2.
M. Gulliksson 《BIT Numerical Mathematics》1994,34(2):239-253
We present an algorithm for mixed precision iterative refinement on the constrained and weighted linear least squares problem, the CWLSQ problem. The approximate solution is obtained by solving the CWLSQ problem with the weightedQR factorization [6]. With backward errors for the weightedQR decomposition together with perturbation bounds for the CWLSQ problem we analyze the convergence behaviour of the iterative refinement procedure.In the unweighted case the initial convergence rate of the error of the iteratively refined solution is determined essentially by the condition number. For the CWLSQ problem the initial convergence behaviour is more complicated. The analysis shows that the initial convergence is dependent both on the condition of the problem related to the solution,x, and the vector =Wr, whereW is the weight matrix andr is the residual.We test our algorithm on two examples where the solution is known and the condition number of the problem can be varied. The computational test confirms the theoretical results and verifies that mixed precision iterative refinement, using the system matrix and the weightedQR decomposition, is an effective way of improving an approximate solution to the CWLSQ problem. 相似文献
3.
The ULV decomposition (ULVD) is an important member of a class of rank-revealing two-sided orthogonal decompositions used to approximate the singular value decomposition (SVD). The problem of adding and deleting rows from the ULVD (called updating and downdating, respectively) is considered. The ULVD can be updated and downdated much faster than the SVD, hence its utility. When updating or downdating the ULVD, it is necessary to compute its numerical rank. In this paper, we propose an efficient algorithm which almost always maintains rank-revealing structure of the decomposition after an update or downdate without standard condition estimation. Moreover, we can monitor the accuracy of the information provided by the ULVD as compared to the SVD by tracking exact Frobenius norms of the two small blocks of the lower triangular factor in the decomposition. 相似文献
4.
Summary. In this paper we develop an efficient Schur complement method for solving the 2D Stokes equation. As a basic algorithm, we
apply a decomposition approach with respect to the trace of the pressure. The alternative stream function-vorticity reduction
is also discussed. The original problem is reduced to solving the equivalent boundary (interface) equation with symmetric
and positive definite operator in the appropriate trace space. We apply a mixed finite element approximation to the interface
operator by
iso
triangular elements and prove the optimal error estimates in the presence of stabilizing bubble functions. The norm equivalences
for the corresponding discrete operators are established. Then we propose an asymptotically optimal compression technique
for the related stiffness matrix (in the absence of bubble functions) providing a sparse factorized approximation to the Schur
complement. In this case, the algorithm is shown to have an optimal complexity of the order , q = 2 or q = 3, depending on the geometry, where N is the number of degrees of freedom on the interface. In the presence of bubble functions, our method has the complexity
arithmetical operations. The Schur complement interface equation is resolved by the PCG iterations with an optimal preconditioner.
Received March 20, 1996 / Revised version received October 28, 1997 相似文献
5.
Numerical computation of an analytic singular value decomposition of a matrix valued function 总被引:1,自引:0,他引:1
Angelika Bunse-Gerstner Ralph Byers Volker Mehrmann Nancy K. Nichols 《Numerische Mathematik》1991,60(1):1-39
Summary This paper extends the singular value decomposition to a path of matricesE(t). An analytic singular value decomposition of a path of matricesE(t) is an analytic path of factorizationsE(t)=X(t)S(t)Y(t)
T whereX(t) andY(t) are orthogonal andS(t) is diagonal. To maintain differentiability the diagonal entries ofS(t) are allowed to be either positive or negative and to appear in any order. This paper investigates existence and uniqueness of analytic SVD's and develops an algorithm for computing them. We show that a real analytic pathE(t) always admits a real analytic SVD, a full-rank, smooth pathE(t) with distinct singular values admits a smooth SVD. We derive a differential equation for the left factor, develop Euler-like and extrapolated Euler-like numerical methods for approximating an analytic SVD and prove that the Euler-like method converges.Partial support received from SFB 343, Diskrete Strukturen in der Mathematik, Universität BielefeldPartial support received from FSP Mathematisierung, Universität BielefeldPartial support received from FSP Mathematisierung, Universität BielefeldPartial support received from National Science Foundation grant CCR-8820882. Some support was also received from the University of Kansas through International Travel Fund 560478 and General Research Allocations # 3758-20-0038 and #3692-20-0038. 相似文献
6.
Summary. In this paper, we are concerned with a matrix equation
where A is an real matrix and x and b are n-vectors. Assume that an approximate solution is given together with an approximate LU decomposition. We will present fast algorithms for proving nonsingularity of A and for calculating rigorous error bounds for . The emphasis is on rigour of the bounds. The purpose of this paper is to propose different algorithms, the fastest with
flops computational cost for the verification step, the same as for the LU decomposition. The presented algorithms exclusively use library routines for LU decomposition and for all other matrix and vector operations.
Received June 16, 1999 / Revised version received January 25, 2001 / Published online June 20, 2001 相似文献
7.
Using domain decomposition to find graph bisectors 总被引:1,自引:0,他引:1
In this paper we introduce a three-step approach to find a vertex bisector of a graph. The first step finds adomain decomposition of the graph, consisting of a set of domains and a multisector. Eachdomain is a connected subgraph, and themultisector contains the remaining vertices that separate the domains from each other. The second step uses a block variant of the Kernighan-Lin
scheme to find a bisector that is a subset of the multisector. The third step improves the bisector by bipartite graph matching.
Experimental results show this domain decomposition method finds graph partitions that compare favorably with a state-of-the-art
multilevel partitioning scheme in both quality and execution time.
This research was supported in part by the ARPA Contract DABT63-95-C-0122, and in part by the Natural Sciences and Engineering
Research Council of Canada under grant A5509. 相似文献
8.
Estimates for the condition number of a matrix are useful in many areas of scientific computing, including: recursive least squares computations, optimization, eigenanalysis, and general nonlinear problems solved by linearization techniques where matrix modification techniques are used. The purpose of this paper is to propose anadaptiveLanczosestimator scheme, which we callale, for tracking the condition number of the modified matrix over time. Applications to recursive least squares (RLS) computations using the covariance method with sliding data windows are considered.ale is fast for relatively smalln-parameter problems arising in RLS methods in control and signal processing, and is adaptive over time, i.e., estimates at timet are used to produce estimates at timet+1. Comparisons are made with other adaptive and non-adaptive condition estimators for recursive least squares problems. Numerical experiments are reported indicating thatale yields a very accurate recursive condition estimator.Research supported by the US Air Force under grant no. AFOSR-88-0285.Research supported by the US Army under grant no. DAAL03-90-G-105.Research supported by the US Air Force under grant no. AFOSR-88-0285. 相似文献
9.
In Demmel et al. (Numer. Math. 106(2), 199–224, 2007) we showed that a large class of fast recursive matrix multiplication
algorithms is stable in a normwise sense, and that in fact if multiplication of n-by-n matrices can be done by any algorithm in O(n
ω+η
) operations for any η > 0, then it can be done stably in O(n
ω+η
) operations for any η > 0. Here we extend this result to show that essentially all standard linear algebra operations, including LU decomposition,
QR decomposition, linear equation solving, matrix inversion, solving least squares problems, (generalized) eigenvalue problems
and the singular value decomposition can also be done stably (in a normwise sense) in O(n
ω+η
) operations.
J. Demmel acknowledges support of NSF under grants CCF-0444486, ACI-00090127, CNS-0325873 and of DOE under grant DE-FC02-01ER25478. 相似文献
10.
The symmetric procrustes problem 总被引:3,自引:0,他引:3
Nicholas J. Higham 《BIT Numerical Mathematics》1988,28(1):133-143
The following symmetric Procrustes problem arises in the determination of the strain matrix of an elastic structure: find the symmetric matrixX which minimises the Frobenius (or Euclidean) norm ofAX — B, whereA andB are given rectangular matrices. We use the singular value decomposition to analyse the problem and to derive a stable method for its solution. A perturbation result is derived and used to assess the stability of methods based on solving normal equations. Some comparisons with the standard, unconstrained least squares problem are given. 相似文献
11.
Nicholas J. Higham 《Numerische Mathematik》1992,62(1):539-555
Summary The Hölderp-norm of anm×n matrix has no explicit representation unlessp=1,2 or . It is shown here that thep-norm can be estimated reliably inO(mn) operations. A generalization of the power method is used, with a starting vector determined by a technique with a condition estimation flavour. The algorithm nearly always computes ap-norm estimate correct to the specified accuracy, and the estimate is always within a factorn
1–1/p
of A
p
. As a by-product, a new way is obtained to estimate the 2-norm of a rectangular matrix; this method is more general and produces better estimates in practice than a similar technique of Cline, Conn and Van Loan. 相似文献
12.
T. Tommasini 《Advances in Computational Mathematics》1996,6(1):77-86
This paper presents a new QRD factorization of a rectangular Vandermonde matrix for a special point distribution, including the symmetric case, based on ak-dimensional block decomposition of the matrix and some properties of the Kronecker product. The computational reduction factor with respect to any QR method isk
2, in the general case, and 4 in the symmetric one. By the resulting matrix factorization, new formulas are devised for the least squares system solution, whose implementation produces an algorithm of reduced computational cost and computer storage. Finally the perturbation bounds of this new factorization are devised. 相似文献
13.
Summary This paper deals with quadratic convergence estimates for the serialJ-symmetric Jacobi method recently proposed by Veseli. The method is characterized by the use of orthogonal and hyperbolic plane rotations. Using a new technique recently introduced by Hari we prove sharp quadratic convergence bounds in the general case of multiple eigenvalues. 相似文献
14.
Wolfgang Hackbusch Boris N. Khoromskij Eugene E. Tyrtyshnikov 《Numerische Mathematik》2008,109(3):365-383
Important matrix-valued functions f (A) are, e.g., the inverse A
−1, the square root and the sign function. Their evaluation for large matrices arising from pdes is not an easy task and needs techniques exploiting
appropriate structures of the matrices A and f (A) (often f (A) possesses this structure only approximately). However, intermediate matrices arising during the evaluation may lose the
structure of the initial matrix. This would make the computations inefficient and even infeasible. However, the main result
of this paper is that an iterative fixed-point like process for the evaluation of f (A) can be transformed, under certain general assumptions, into another process which preserves the convergence rate and benefits
from the underlying structure. It is shown how this result applies to matrices in a tensor format with a bounded tensor rank
and to the structure of the hierarchical matrix technique. We demonstrate our results by verifying all requirements in the
case of the iterative computation of A
−1 and .
This work was performed during the stay of the third author at the Max-Planck-Institute for Mathematics in the Sciences (Leipzig)
and also supported by the Russian Fund of Basic Research (grants 05-01-00721, 04-07-90336) and a Priority Research Grant of
the Department of Mathematical Sciences of the Russian Academy of Sciences. 相似文献
15.
Fierro Ricardo D. Hansen Per Christian Hansen Peter Søren Kirk 《Numerical Algorithms》1999,20(2-3):165-194
We describe a Matlab 5.2 package for computing and modifying certain rank-revealing decompositions that have found widespread
use in signal processing and other applications. The package focuses on algorithms for URV and ULV decompositions, collectively
known as UTV decompositions. We include algorithms for the ULLV decomposition, which generalizes the ULV decomposition to
a pair of matrices. For completeness a few algorithms for computation of the RRQR decomposition are also included. The software
in this package can be used as is, or can be considered as templates for specialized implementations on signal processors
and similar dedicated hardware platforms.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
16.
Summary We show that the greedy algorithm introduced in [1] and [5] to perform the parallel QR decomposition of a dense rectangular matrix of sizem×n is optimal. Then we assume thatm/n
2 tends to zero asm andn go to infinity, and prove that the complexity of such a decomposition is asymptotically2n, when an unlimited number of processors is available. 相似文献
17.
Summary Based on the framework of subspace splitting and the additive Schwarz scheme, we give bounds for the condition number of multilevel preconditioners for sparse grid discretizations of elliptic model problems. For a BXP-like preconditioner we derive an estimate of the optimal orderO(1) and for a HB-like variant we obtain an estimate of the orderO(k
2
·2
k/2
), wherek denotes the number of levels employed. Furthermore, we confirm these results by numerically computed condition numbers. 相似文献
18.
Thomas Huckle 《BIT Numerical Mathematics》1994,34(1):99-112
In this paper we study the use of the Fourier, Sine and Cosine Transform for solving or preconditioning linear systems, which arise from the discretization of elliptic problems. Recently, R. Chan and T. Chan considered circulant matrices for solving such systems. Instead of using circulant matrices, which are based on the Fourier Transform, we apply the Fourier and the Sine Transform directly. It is shown that tridiagonal matrices arising from the discretization of an onedimensional elliptic PDE are connected with circulant matrices by congruence transformations with the Fourier or the Sine matrix. Therefore, we can solve such linear systems directly, using only Fast Fourier Transforms and the Sherman-Morrison-Woodbury formula. The Fast Fourier Transform is highly parallelizable, and thus such an algorithm is interesting on a parallel computer. Moreover, similar relations hold between block tridiagonal matrices and Block Toeplitz-plus-Hankel matrices of ordern
2×n
2 in the 2D case. This can be used to define in some sense natural approximations to the given matrix which lead to preconditioners for solving such linear systems. 相似文献
19.
Tommy Elfving 《BIT Numerical Mathematics》1998,38(2):275-282
Iterative methods applied to the normal equationsA
T
Ax=A
T
b are sometimes used for solving large sparse linear least squares problems. However, when the matrix is rank-deficient many
methods, although convergent, fail to produce the unique solution of minimal Euclidean norm. Examples of such methods are
the Jacobi and SOR methods as well as the preconditioned conjugate gradient algorithm. We analyze here an iterative scheme
that overcomes this difficulty for the case of stationary iterative methods. The scheme combines two stationary iterative
methods. The first method produces any least squares solution whereas the second produces the minimum norm solution to a consistent
system.
This work was supported by the Swedish Research Council for Engineering Sciences, TFR. 相似文献
20.
The application of the Lanczos algorithm in Newton-like methods for solving non-linear systems of equations arising in nonlinear
structural finite element analysis is presented. It is shown that with appropriate preconditioners iterative methods can be
developed which are robust and efficient even for ill conditioned problems. Though the real advantage of iterative solvers
seems to exist on distributed memory machines, even on serial machines the performance can be improved compared with direct
solvers while saving memory capacity. With a specific modification of the Lanczos algorithm in combination with arc-length
procedures a further speed-up of the nonlinear analysis can be achieved.
For parallel implementations domain decomposition methods are used. A parallel preconditioning strategy based on an incomplete
factorisation method is presented. An example is taken and the quality and efficiency of two different domain decomposition
methods are discussed for a large shell structure.
This work was supported by the BMBF (Bundesministerium für Bildung und Forschung) of Germany. 相似文献