Preconditioned Krylov subspace methods for eigenvalue problems
Wu, Kesheng; Saad, Y.; Stathopoulos, A.
1996-12-31
Lanczos algorithm is a commonly used method for finding a few extreme eigenvalues of symmetric matrices. It is effective if the wanted eigenvalues have large relative separations. If separations are small, several alternatives are often used, including the shift-invert Lanczos method, the preconditioned Lanczos method, and Davidson method. The shift-invert Lanczos method requires direct factorization of the matrix, which is often impractical if the matrix is large. In these cases preconditioned schemes are preferred. Many applications require solution of hundreds or thousands of eigenvalues of large sparse matrices, which pose serious challenges for both iterative eigenvalue solver and preconditioner. In this paper we will explore several preconditioned eigenvalue solvers and identify the ones suited for finding large number of eigenvalues. Methods discussed in this paper make up the core of a preconditioned eigenvalue toolkit under construction.
Preserving Symmetry in Preconditioned Krylov Subspace Methods
NASA Technical Reports Server (NTRS)
Chan, Tony F.; Chow, E.; Saad, Y.; Yeung, M. C.
1996-01-01
We consider the problem of solving a linear system Ax = b when A is nearly symmetric and when the system is preconditioned by a symmetric positive definite matrix M. In the symmetric case, one can recover symmetry by using M-inner products in the conjugate gradient (CG) algorithm. This idea can also be used in the nonsymmetric case, and near symmetry can be preserved similarly. Like CG, the new algorithms are mathematically equivalent to split preconditioning, but do not require M to be factored. Better robustness in a specific sense can also be observed. When combined with truncated versions of iterative methods, tests show that this is more effective than the common practice of forfeiting near-symmetry altogether.
Pipelined Flexible Krylov Subspace Methods
NASA Astrophysics Data System (ADS)
Sanan, Patrick; Schnepp, Sascha M.; May, Dave A.
2015-04-01
State-of-the-art geophysical forward models expend most of their computational resources solving large, sparse linear systems. To date, preconditioned Krylov subspace methods have proven to be the only algorithmically scalable approach to solving these systems. However, at `extreme scale', the global reductions required by the inner products within these algorithms become a computational bottleneck, and it becomes advantageous to use pipelined Krylov subspace methods. These allow overlap of global reductions with other work, at the expense of using more storage and local computational effort, including overhead required to synchronize overlapping work. An impediment to using currently-available pipelined solvers for relevant geophysical forward modeling is that they are not `flexible', meaning that they cannot support nonlinear or varying preconditioners. Such preconditioners are effective for solving challenging linear systems, notably those arising from modelling of Stokes flow with highly heterogeneous viscosity structure. To this end, we introduce, for the first time, Krylov subspace methods which are both pipelined and flexible. We implement and demonstrate pipelined, flexible Conjugate Gradient, GMRES, and Conjugate Residual methods, which will be made publicly available via the open source PETSc library. Our algorithms are nontrivial modifications of the flexible methods they are based on (that is, they are not equivalent in exact arithmetic), so we analyze them mathematically and through a number of numerical experiments employing multi-level preconditioners. We highlight the benefits of these algorithms by solving variable viscosity Stokes problems directly relevant to lithospheric dynamics.
Krylov subspace methods on supercomputers
NASA Technical Reports Server (NTRS)
Saad, Youcef
1988-01-01
A short survey of recent research on Krylov subspace methods with emphasis on implementation on vector and parallel computers is presented. Conjugate gradient methods have proven very useful on traditional scalar computers, and their popularity is likely to increase as three-dimensional models gain importance. A conservative approach to derive effective iterative techniques for supercomputers has been to find efficient parallel/vector implementations of the standard algorithms. The main source of difficulty in the incomplete factorization preconditionings is in the solution of the triangular systems at each step. A few approaches consisting of implementing efficient forward and backward triangular solutions are described in detail. Polynomial preconditioning as an alternative to standard incomplete factorization techniques is also discussed. Another efficient approach is to reorder the equations so as to improve the structure of the matrix to achieve better parallelism or vectorization. An overview of these and other ideas and their effectiveness or potential for different types of architectures is given.
Krylov subspace methods - Theory, algorithms, and applications
NASA Technical Reports Server (NTRS)
Sad, Youcef
1990-01-01
Projection methods based on Krylov subspaces for solving various types of scientific problems are reviewed. The main idea of this class of methods when applied to a linear system Ax = b, is to generate in some manner an approximate solution to the original problem from the so-called Krylov subspace span. Thus, the original problem of size N is approximated by one of dimension m, typically much smaller than N. Krylov subspace methods have been very successful in solving linear systems and eigenvalue problems and are now becoming popular for solving nonlinear equations. The main ideas in Krylov subspace methods are shown and their use in solving linear systems, eigenvalue problems, parabolic partial differential equations, Liapunov matrix equations, and nonlinear system of equations are discussed.
Overview of Krylov subspace methods with applications to control problems
NASA Technical Reports Server (NTRS)
Saad, Youcef
1989-01-01
An overview of projection methods based on Krylov subspaces are given with emphasis on their application to solving matrix equations that arise in control problems. The main idea of Krylov subspace methods is to generate a basis of the Krylov subspace Span and seek an approximate solution the the original problem from this subspace. Thus, the original matrix problem of size N is approximated by one of dimension m typically much smaller than N. Krylov subspace methods have been very successful in solving linear systems and eigenvalue problems and are now just becoming popular for solving nonlinear equations. It is shown how they can be used to solve partial pole placement problems, Sylvester's equation, and Lyapunov's equation.
Solving nonlinear heat conduction problems with multigrid preconditioned Newton-Krylov methods
Rider, W.J.; Knoll, D.A.
1997-09-01
Our objective is to investigate the utility of employing multigrid preconditioned Newton-Krylov methods for solving initial value problems. Multigrid based method promise better performance from the linear scaling associated with them. Our model problem is nonlinear heat conduction which can model idealized Marshak waves. Here we will investigate the efficiency of using a linear multigrid method to precondition a Krylov subspace method. In effect we will show that a fixed point nonlinear iterative method provides an effective preconditioner for the nonlinear problem.
Reduced-Rank Adaptive Filtering Using Krylov Subspace
NASA Astrophysics Data System (ADS)
Burykh, Sergueï; Abed-Meraim, Karim
2003-12-01
A unified view of several recently introduced reduced-rank adaptive filters is presented. As all considered methods use Krylov subspace for rank reduction, the approach taken in this work is inspired from Krylov subspace methods for iterative solutions of linear systems. The alternative interpretation so obtained is used to study the properties of each considered technique and to relate one reduced-rank method to another as well as to algorithms used in computational linear algebra. Practical issues are discussed and low-complexity versions are also included in our study. It is believed that the insight developed in this paper can be further used to improve existing reduced-rank methods according to known results in the domain of Krylov subspace methods.
Krylov-subspace acceleration of time periodic waveform relaxation
Lumsdaine, A.
1994-12-31
In this paper the author uses Krylov-subspace techniques to accelerate the convergence of waveform relaxation applied to solving systems of first order time periodic ordinary differential equations. He considers the problem in the frequency domain and presents frequency dependent waveform GMRES (FDWGMRES), a member of a new class of frequency dependent Krylov-subspace techniques. FDWGMRES exhibits many desirable properties, including finite termination independent of the number of timesteps and, for certain problems, a convergence rate which is bounded from above by the convergence rate of GMRES applied to the static matrix problem corresponding to the linear time-invariant ODE.
An adaptation of Krylov subspace methods to path following
Walker, H.F.
1996-12-31
Krylov subspace methods at present constitute a very well known and highly developed class of iterative linear algebra methods. These have been effectively applied to nonlinear system solving through Newton-Krylov methods, in which Krylov subspace methods are used to solve the linear systems that characterize steps of Newton`s method (the Newton equations). Here, we will discuss the application of Krylov subspace methods to path following problems, in which the object is to track a solution curve as a parameter varies. Path following methods are typically of predictor-corrector form, in which a point near the solution curve is {open_quotes}predicted{close_quotes} by some easy but relatively inaccurate means, and then a series of Newton-like corrector iterations is used to return approximately to the curve. The analogue of the Newton equation is underdetermined, and an additional linear condition must be specified to determine corrector steps uniquely. This is typically done by requiring that the steps be orthogonal to an approximate tangent direction. Augmenting the under-determined system with this orthogonality condition in a straightforward way typically works well if direct linear algebra methods are used, but Krylov subspace methods are often ineffective with this approach. We will discuss recent work in which this orthogonality condition is imposed directly as a constraint on the corrector steps in a certain way. The means of doing this preserves problem conditioning, allows the use of preconditioners constructed for the fixed-parameter case, and has certain other advantages. Experiments on standard PDE continuation test problems indicate that this approach is effective.
NASA Astrophysics Data System (ADS)
Gatsis, John
An investigation of preconditioning techniques is presented for a Newton-Krylov algorithm that is used for the computation of steady, compressible, high Reynolds number flows about airfoils. A second-order centred-difference method is used to discretize the compressible Navier-Stokes (NS) equations that govern the fluid flow. The one-equation Spalart-Allmaras turbulence model is used. The discretized equations are solved using Newton's method and the generalized minimal residual (GMRES) Krylov subspace method is used to approximately solve the linear system. These preconditioning techniques are first applied to the solution of the discretized steady convection-diffusion equation. Various orderings, iterative block incomplete LU (BILU) preconditioning and multigrid preconditioning are explored. The baseline preconditioner is a BILU factorization of a lower-order discretization of the system matrix in the Newton linearization. An ordering based on the minimum discarded fill (MDF) ordering is developed and compared to the widely popular reverse Cuthill-McKee ordering. An evolutionary algorithm is used to investigate and enhance this ordering. For the convection-diffusion equation, the MDF-based ordering performs well and RCM is superior for the NS equations. Experiments for inviscid, laminar and turbulent cases are presented to show the effectiveness of iterative BILU preconditioning in terms of reducing the number of GMRES iterations, and hence the memory requirements of the Newton-Krylov algorithm. Multigrid preconditioning also reduces the number of GMRES iterations. The framework for the iterative BILU and BILU-smoothed multigrid preconditioning algorithms is presented in detail.
Application of Block Krylov Subspace Spectral Methods to Maxwell's Equations
Lambers, James V.
2009-10-08
Ever since its introduction by Kane Yee over forty years ago, the finite-difference time-domain (FDTD) method has been a widely-used technique for solving the time-dependent Maxwell's equations. This paper presents an alternative approach to these equations in the case of spatially-varying electric permittivity and/or magnetic permeability, based on Krylov subspace spectral (KSS) methods. These methods have previously been applied to the variable-coefficient heat equation and wave equation, and have demonstrated high-order accuracy, as well as stability characteristic of implicit time-stepping schemes, even though KSS methods are explicit. KSS methods for scalar equations compute each Fourier coefficient of the solution using techniques developed by Gene Golub and Gerard Meurant for approximating elements of functions of matrices by Gaussian quadrature in the spectral, rather than physical, domain. We show how they can be generalized to coupled systems of equations, such as Maxwell's equations, by choosing appropriate basis functions that, while induced by this coupling, still allow efficient and robust computation of the Fourier coefficients of each spatial component of the electric and magnetic fields. We also discuss the implementation of appropriate boundary conditions for simulation on infinite computational domains, and how discontinuous coefficients can be handled.
Domain decomposed preconditioners with Krylov subspace methods as subdomain solvers
Pernice, M.
1994-12-31
Domain decomposed preconditioners for nonsymmetric partial differential equations typically require the solution of problems on the subdomains. Most implementations employ exact solvers to obtain these solutions. Consequently work and storage requirements for the subdomain problems grow rapidly with the size of the subdomain problems. Subdomain solves constitute the single largest computational cost of a domain decomposed preconditioner, and improving the efficiency of this phase of the computation will have a significant impact on the performance of the overall method. The small local memory available on the nodes of most message-passing multicomputers motivates consideration of the use of an iterative method for solving subdomain problems. For large-scale systems of equations that are derived from three-dimensional problems, memory considerations alone may dictate the need for using iterative methods for the subdomain problems. In addition to reduced storage requirements, use of an iterative solver on the subdomains allows flexibility in specifying the accuracy of the subdomain solutions. Substantial savings in solution time is possible if the quality of the domain decomposed preconditioner is not degraded too much by relaxing the accuracy of the subdomain solutions. While some work in this direction has been conducted for symmetric problems, similar studies for nonsymmetric problems appear not to have been pursued. This work represents a first step in this direction, and explores the effectiveness of performing subdomain solves using several transpose-free Krylov subspace methods, GMRES, transpose-free QMR, CGS, and a smoothed version of CGS. Depending on the difficulty of the subdomain problem and the convergence tolerance used, a reduction in solution time is possible in addition to the reduced memory requirements. The domain decomposed preconditioner is a Schur complement method in which the interface operators are approximated using interface probing.
Krylov subspace methods for computing hydrodynamic interactions in Brownian dynamics simulations
Ando, Tadashi; Chow, Edmond; Saad, Yousef; Skolnick, Jeffrey
2012-01-01
Hydrodynamic interactions play an important role in the dynamics of macromolecules. The most common way to take into account hydrodynamic effects in molecular simulations is in the context of a Brownian dynamics simulation. However, the calculation of correlated Brownian noise vectors in these simulations is computationally very demanding and alternative methods are desirable. This paper studies methods based on Krylov subspaces for computing Brownian noise vectors. These methods are related to Chebyshev polynomial approximations, but do not require eigenvalue estimates. We show that only low accuracy is required in the Brownian noise vectors to accurately compute values of dynamic and static properties of polymer and monodisperse suspension models. With this level of accuracy, the computational time of Krylov subspace methods scales very nearly as O(N2) for the number of particles N up to 10 000, which was the limit tested. The performance of the Krylov subspace methods, especially the “block” version, is slightly better than that of the Chebyshev method, even without taking into account the additional cost of eigenvalue estimates required by the latter. Furthermore, at N = 10 000, the Krylov subspace method is 13 times faster than the exact Cholesky method. Thus, Krylov subspace methods are recommended for performing large-scale Brownian dynamics simulations with hydrodynamic interactions. PMID:22897254
Druskin, V.; Lee, Ping; Knizhnerman, L.
1996-12-31
There is now a growing interest in the area of using Krylov subspace approximations to compute the actions of matrix functions. The main application of this approach is the solution of ODE systems, obtained after discretization of partial differential equations by method of lines. In the event that the cost of computing the matrix inverse is relatively inexpensive, it is sometimes attractive to solve the ODE using the extended Krylov subspaces, originated by actions of both positive and negative matrix powers. Examples of such problems can be found frequently in computational electromagnetics.
A subspace preconditioning algorithm for eigenvector/eigenvalue computation
Bramble, J.H.; Knyazev, A.V.; Pasciak, J.E.
1996-12-31
We consider the problem of computing a modest number of the smallest eigenvalues along with orthogonal bases for the corresponding eigen-spaces of a symmetric positive definite matrix. In our applications, the dimension of a matrix is large and the cost of its inverting is prohibitive. In this paper, we shall develop an effective parallelizable technique for computing these eigenvalues and eigenvectors utilizing subspace iteration and preconditioning. Estimates will be provided which show that the preconditioned method converges linearly and uniformly in the matrix dimension when used with a uniform preconditioner under the assumption that the approximating subspace is close enough to the span of desired eigenvectors.
A linear system solver based on a modified Krylov subspace method for breakdown recovery
NASA Astrophysics Data System (ADS)
Tong, Charles; Ye, Qiang
1996-03-01
Despite its usefulness in solving eigenvalue problems and linear systems of equations, the nonsymmetric Lanczos method is known to suffer from a potential breakdown problem. Previous and recent approaches for handling the Lanczos exact and near-breakdowns include, for example, the look-ahead schemes by Parlett-Taylor-Liu [23], Freund-Gutknecht-Nachtigal [9], and Brezinski-Redivo Zaglia-Sadok [4]; the combined look-ahead and restart scheme by Joubert [18]; and the low-rank modified Lanczos scheme by Huckle [17]. In this paper, we present yet another scheme based on a modified Krylov subspace approach for the solution of nonsymmetric linear systems. When a breakdown occurs, our approach seeks a modified dual Krylov subspace, which is the sum of the original subspace and a new Krylov subspaceKm(wj,AT) wherewj is a newstart vector (this approach has been studied by Ye [26] for eigenvalue computations). Based on this strategy, we have developed a practical algorithm for linear systems called the MLAN/QM algorithm, which also incorporates the residual quasi-minimization as proposed in [12]. We present a few convergence bounds for the method as well as numerical results to show its effectiveness.
A hierarchical Krylov-Bayes iterative inverse solver for MEG with physiological preconditioning
NASA Astrophysics Data System (ADS)
Calvetti, D.; Pascarella, A.; Pitolli, F.; Somersalo, E.; Vantaggi, B.
2015-12-01
The inverse problem of MEG aims at estimating electromagnetic cerebral activity from measurements of the magnetic fields outside the head. After formulating the problem within the Bayesian framework, a hierarchical conditionally Gaussian prior model is introduced, including a physiologically inspired prior model that takes into account the preferred directions of the source currents. The hyperparameter vector consists of prior variances of the dipole moments, assumed to follow a non-conjugate gamma distribution with variable scaling and shape parameters. A point estimate of both dipole moments and their variances can be computed using an iterative alternating sequential updating algorithm, which is shown to be globally convergent. The numerical solution is based on computing an approximation of the dipole moments using a Krylov subspace iterative linear solver equipped with statistically inspired preconditioning and a suitable termination rule. The shape parameters of the model are shown to control the focality, and furthermore, using an empirical Bayes argument, it is shown that the scaling parameters can be naturally adjusted to provide a statistically well justified depth sensitivity scaling. The validity of this interpretation is verified through computed numerical examples. Also, a computed example showing the applicability of the algorithm to analyze realistic time series data is presented.
Generalization of the residual cutting method based on the Krylov subspace
NASA Astrophysics Data System (ADS)
Abe, Toshihiko; Sekine, Yoshihito; Kikuchi, Kazuo
2016-06-01
The residual cutting (RC) method has been reported to have superior converging characteristics in numerically solving elliptic partial differential equations. However, its application is limited to linear problems with diagonal-dominant matrices in general, for which convergence of a relaxation method such as SOR is guaranteed. In this study, we propose the generalized residual cutting (GRC) method, which is based on the Krylov subspace and applicable to general unsymmetric linear problems. Also, we perform numerical experiments with various coefficient matrices, and show that the GRC method has some desirable properties such as convergence characteristics and memory usage, in comparison to the conventional RC, BiCGSTAB and GMRES methods.
Krylov subspace algorithms for computing GeneRank for the analysis of microarray data mining.
Wu, Gang; Zhang, Ying; Wei, Yimin
2010-04-01
GeneRank is a new engine technology for the analysis of microarray experiments. It combines gene expression information with a network structure derived from gene notations or expression profile correlations. Using matrix decomposition techniques, we first give a matrix analysis of the GeneRank model. We reformulate the GeneRank vector as a linear combination of three parts in the general case when the matrix in question is non-diagonalizable. We then propose two Krylov subspace methods for computing GeneRank. Numerical experiments show that, when the GeneRank problem is very large, the new algorithms are appropriate choices. PMID:20426695
A General Algorithm for Reusing Krylov Subspace Information. I. Unsteady Navier-Stokes
NASA Technical Reports Server (NTRS)
Carpenter, Mark H.; Vuik, C.; Lucas, Peter; vanGijzen, Martin; Bijl, Hester
2010-01-01
A general algorithm is developed that reuses available information to accelerate the iterative convergence of linear systems with multiple right-hand sides A x = b (sup i), which are commonly encountered in steady or unsteady simulations of nonlinear equations. The algorithm is based on the classical GMRES algorithm with eigenvector enrichment but also includes a Galerkin projection preprocessing step and several novel Krylov subspace reuse strategies. The new approach is applied to a set of test problems, including an unsteady turbulent airfoil, and is shown in some cases to provide significant improvement in computational efficiency relative to baseline approaches.
Druskin, V.; Knizhnerman, L.
1994-12-31
The authors solve the Cauchy problem for an ODE system Au + {partial_derivative}u/{partial_derivative}t = 0, u{vert_bar}{sub t=0} = {var_phi}, where A is a square real nonnegative definite symmetric matrix of the order N, {var_phi} is a vector from R{sup N}. The stiffness matrix A is obtained due to semi-discretization of a parabolic equation or system with time-independent coefficients. The authors are particularly interested in large stiff 3-D problems for the scalar diffusion and vectorial Maxwell`s equations. First they consider an explicit method in which the solution on a whole time interval is projected on a Krylov subspace originated by A. Then they suggest another Krylov subspace with better approximating properties using powers of an implicit transition operator. These Krylov subspace methods generate optimal in a spectral sense polynomial approximations for the solution of the ODE, similar to CG for SLE.
A numerical solution of a Cauchy problem for an elliptic equation by Krylov subspaces
NASA Astrophysics Data System (ADS)
Eldén, Lars; Simoncini, Valeria
2009-06-01
We study the numerical solution of a Cauchy problem for a self-adjoint elliptic partial differential equation uzz - Lu = 0 in three space dimensions (x, y, z), where the domain is cylindrical in z. Cauchy data are given on the lower boundary and the boundary values on the upper boundary are sought. The problem is severely ill-posed. The formal solution is written as a hyperbolic cosine function in terms of the two-dimensional elliptic operator L (via its eigenfunction expansion), and it is shown that the solution is stabilized (regularized) if the large eigenvalues are cut off. We suggest a numerical procedure based on the rational Krylov method, where the solution is projected onto a subspace generated using the operator L-1. This means that in each Krylov step, a well-posed two-dimensional elliptic problem involving L is solved. Furthermore, the hyperbolic cosine is evaluated explicitly only for a small symmetric matrix. A stopping criterion for the Krylov recursion is suggested based on the relative change of an approximate residual, which can be computed very cheaply. Two numerical examples are given that demonstrate the accuracy of the method and the efficiency of the stopping criterion.
Krylov subspace iterative methods for boundary element method based near-field acoustic holography.
Valdivia, Nicolas; Williams, Earl G
2005-02-01
The reconstruction of the acoustic field for general surfaces is obtained from the solution of a matrix system that results from a boundary integral equation discretized using boundary element methods. The solution to the resultant matrix system is obtained using iterative regularization methods that counteract the effect of noise on the measurements. These methods will not require the calculation of the singular value decomposition, which can be expensive when the matrix system is considerably large. Krylov subspace methods are iterative methods that have the phenomena known as "semi-convergence," i.e., the optimal regularization solution is obtained after a few iterations. If the iteration is not stopped, the method converges to a solution that generally is totally corrupted by errors on the measurements. For these methods the number of iterations play the role of the regularization parameter. We will focus our attention to the study of the regularizing properties from the Krylov subspace methods like conjugate gradients, least squares QR and the recently proposed Hybrid method. A discussion and comparison of the available stopping rules will be included. A vibrating plate is considered as an example to validate our results. PMID:15759691
3D-marine tCSEM inversion using model reduction in the Rational Krylov subspace
NASA Astrophysics Data System (ADS)
Sommer, M.; Jegen, M. D.
2014-12-01
Computationally, the most expensive part of a 3D time domain CSEM inversion is the computation of the Jacobian matrix in every Gauss-Newton step. An other problem is its size for large data sets. We use a model reduction method (Zaslavsky et al, 2013), that compresses the Jacobian by projecting it with a Rational Krylov Subspace (RKS). It also reduces the runtime drastically, compared to the most common adjoint approach and was implemented on GPU.It depends on an analytic derivation of the implicit Anzatz function, which solves Maxwell's diffusion equation in the Eigenspace giving a Jacobian dependent on the Eigenpairs and its derivatives of the forward problem. The Eigenpairs are approximated by Ritz-pairs in the Rational Krylov subspace. Determination of the derivived Ritz-pairs is the most time consuming and was fully GPU-optimized. Furthermore, the amount of inversion cells is reduced by using Octree meshes. The gridding allows for the incorporation of complicated survey geometries, as they are encountered in marine CSEM datasets.As a first result, the Jacobian computation is, even on a Desktop, faster than the most common adjoint approach on a super computer for realistic data sets. We will present careful benchmarking and accuracy tests of the new method and show how it can be applied to a real marine scenario.
A new Krylov-subspace method for symmetric indefinite linear systems
Freund, R.W.; Nachtigal, N.M.
1994-10-01
Many important applications involve the solution of large linear systems with symmetric, but indefinite coefficient matrices. For example, such systems arise in incompressible flow computations and as subproblems in optimization algorithms for linear and nonlinear programs. Existing Krylov-subspace iterations for symmetric indefinite systems, such as SYMMLQ and MINRES, require the use of symmetric positive definite preconditioners, which is a rather unnatural restriction when the matrix itself is highly indefinite with both many positive and many negative eigenvalues. In this note, the authors describe a new Krylov-subspace iteration for solving symmetric indefinite linear systems that can be combined with arbitrary symmetric preconditioners. The algorithm can be interpreted as a special case of the quasi-minimal residual method for general non-Hermitian linear systems, and like the latter, it produces iterates defined by a quasi-minimal residual property. The proposed method has the same work and storage requirements per iteration as SYMMLQ or MINRES, however, it usually converges in considerably fewer iterations. Results of numerical experiments are reported.
Generalization of the residual cutting method based on the Krylov subspace
NASA Astrophysics Data System (ADS)
Abe, Toshihiko; Sekine, Yoshihito; Kikuchi, Kazuo
2016-06-01
The residual cutting (RC) method has been reported to have superior converging characteristics in numerically solving elliptic partial differential equations. However, its application is limited to linear problems with diagonal-dominant matrices in general, for which convergence of a relaxation method such as SOR is guaranteed. In this study, we propose the generalized residual cutting (GRC) method, which is based on the Krylov subspace and applicable to general unsymmetric linear problems. Also, we perform numerical experiments with various coefficient matrices, and show that the GRC method has some desirable properties such as convergence characteristics and memory usage, in comparison to the conventional RC, BiCGSTAB and GMRES methods. At the request of the author of this paper, a corrigendum was issued on 22 June 2016 to correct an error in Eq. (2) and Eq. (3).
NASA Technical Reports Server (NTRS)
Sidi, Avram
1992-01-01
Let F(z) be a vectored-valued function F: C approaches C sup N, which is analytic at z=0 and meromorphic in a neighborhood of z=0, and let its Maclaurin series be given. We use vector-valued rational approximation procedures for F(z) that are based on its Maclaurin series in conjunction with power iterations to develop bona fide generalizations of the power method for an arbitrary N X N matrix that may be diagonalizable or not. These generalizations can be used to obtain simultaneously several of the largest distinct eigenvalues and the corresponding invariant subspaces, and present a detailed convergence theory for them. In addition, it is shown that the generalized power methods of this work are equivalent to some Krylov subspace methods, among them the methods of Arnoldi and Lanczos. Thus, the theory provides a set of completely new results and constructions for these Krylov subspace methods. This theory suggests at the same time a new mode of usage for these Krylov subspace methods that were observed to possess computational advantages over their common mode of usage.
Radio astronomical image formation using constrained least squares and Krylov subspaces
NASA Astrophysics Data System (ADS)
Mouri Sardarabadi, Ahmad; Leshem, Amir; van der Veen, Alle-Jan
2016-04-01
Aims: Image formation for radio astronomy can be defined as estimating the spatial intensity distribution of celestial sources throughout the sky, given an array of antennas. One of the challenges with image formation is that the problem becomes ill-posed as the number of pixels becomes large. The introduction of constraints that incorporate a priori knowledge is crucial. Methods: In this paper we show that in addition to non-negativity, the magnitude of each pixel in an image is also bounded from above. Indeed, the classical "dirty image" is an upper bound, but a much tighter upper bound can be formed from the data using array processing techniques. This formulates image formation as a least squares optimization problem with inequality constraints. We propose to solve this constrained least squares problem using active set techniques, and the steps needed to implement it are described. It is shown that the least squares part of the problem can be efficiently implemented with Krylov-subspace-based techniques. We also propose a method for correcting for the possible mismatch between source positions and the pixel grid. This correction improves both the detection of sources and their estimated intensities. The performance of these algorithms is evaluated using simulations. Results: Based on parametric modeling of the astronomical data, a new imaging algorithm based on convex optimization, active sets, and Krylov-subspace-based solvers is presented. The relation between the proposed algorithm and sequential source removing techniques is explained, and it gives a better mathematical framework for analyzing existing algorithms. We show that by using the structure of the algorithm, an efficient implementation that allows massive parallelism and storage reduction is feasible. Simulations are used to compare the new algorithm to classical CLEAN. Results illustrate that for a discrete point model, the proposed algorithm is capable of detecting the correct number of sources
Krylov methods preconditioned with incompletely factored matrices on the CM-2
NASA Technical Reports Server (NTRS)
Berryman, Harry; Saltz, Joel; Gropp, William; Mirchandaney, Ravi
1989-01-01
The performance is measured of the components of the key interative kernel of a preconditioned Krylov space interative linear system solver. In some sense, these numbers can be regarded as best case timings for these kernels. Sweeps were timed over meshes, sparse triangular solves, and inner products on a large 3-D model problem over a cube shaped domain discretized with a seven point template. The performance of the CM-2 is highly dependent on the use of very specialized programs. These programs mapped a regular problem domain onto the processor topology in a careful manner and used the optimized local NEWS communications network. The rather dramatic deterioration in performance was documented when these ideal conditions no longer apply. A synthetic workload generator was developed to produce and solve a parameterized family of increasingly irregular problems.
Comparison of Krylov subspace methods on the PageRank problem
NASA Astrophysics Data System (ADS)
Del Corso, Gianna M.; Gulli, Antonio; Romani, Francesco
2007-12-01
PageRank algorithm plays a very important role in search engine technology and consists in the computation of the eigenvector corresponding to the eigenvalue one of a matrix whose size is now in the billions. The problem incorporates a parameter [alpha] that determines the difficulty of the problem. In this paper, the effectiveness of stationary and nonstationary methods are compared on some portion of real web matrices for different choices of [alpha]. We see that stationary methods are very reliable and more competitive when the problem is well conditioned, that is for small values of [alpha]. However, for large values of the parameter [alpha] the problem becomes more difficult and methods such as preconditioned BiCGStab or restarted preconditioned GMRES become competitive with stationary methods in terms of Mflops count as well as in number of iterations necessary to reach convergence.
ODE System Solver W. Krylov Iteration & Rootfinding
Hindmarsh, Alan C.
1991-09-09
LSODKR is a new initial value ODE solver for stiff and nonstiff systems. It is a variant of the LSODPK and LSODE solvers, intended mainly for large stiff systems. The main differences between LSODKR and LSODE are the following: (a) for stiff systems, LSODKR uses a corrector iteration composed of Newton iteration and one of four preconditioned Krylov subspace iteration methods. The user must supply routines for the preconditioning operations, (b) Within the corrector iteration, LSODKR does automatic switching between functional (fixpoint) iteration and modified Newton iteration, (c) LSODKR includes the ability to find roots of given functions of the solution during the integration.
ODE System Solver W. Krylov Iteration & Rootfinding
Energy Science and Technology Software Center (ESTSC)
1991-09-09
LSODKR is a new initial value ODE solver for stiff and nonstiff systems. It is a variant of the LSODPK and LSODE solvers, intended mainly for large stiff systems. The main differences between LSODKR and LSODE are the following: (a) for stiff systems, LSODKR uses a corrector iteration composed of Newton iteration and one of four preconditioned Krylov subspace iteration methods. The user must supply routines for the preconditioning operations, (b) Within the corrector iteration,more » LSODKR does automatic switching between functional (fixpoint) iteration and modified Newton iteration, (c) LSODKR includes the ability to find roots of given functions of the solution during the integration.« less
Jiang, Mingfeng; Xia, Ling; Huang, Wenqing; Shou, Guofa; Liu, Feng; Crozier, Stuart
2009-10-01
Regularization is an effective method for the solution of ill-posed ECG inverse problems, such as computing epicardial potentials from body surface potentials. The aim of this work was to explore more robust regularization-based solutions through the application of subspace preconditioned LSQR (SP-LSQR) to the study of model-based ECG inverse problems. Here, we presented three different subspace splitting methods, i.e., SVD, wavelet transform and cosine transform schemes, to the design of the preconditioners for ill-posed problems, and to evaluate the performance of algorithms using a realistic heart-torso model simulation protocol. The results demonstrated that when compared with the LSQR, LSQR-Tik and Tik-LSQR method, the SP-LSQR produced higher efficiency and reconstructed more accurate epcicardial potential distributions. Amongst the three applied subspace splitting schemes, the SVD-based preconditioner yielded the best convergence rate and outperformed the other two in seeking the inverse solutions. Moreover, when optimized by the genetic algorithms (GA), the performances of SP-LSQR method were enhanced. The results from this investigation suggested that the SP-LSQR was a useful regularization technique for cardiac inverse problems. PMID:19564127
Luanjing Guo; Chuan Lu; Hai Huang; Derek R. Gaston
2012-06-01
Systems of multicomponent reactive transport in porous media that are large, highly nonlinear, and tightly coupled due to complex nonlinear reactions and strong solution-media interactions are often described by a system of coupled nonlinear partial differential algebraic equations (PDAEs). A preconditioned Jacobian-Free Newton-Krylov (JFNK) solution approach is applied to solve the PDAEs in a fully coupled, fully implicit manner. The advantage of the JFNK method is that it avoids explicitly computing and storing the Jacobian matrix during Newton nonlinear iterations for computational efficiency considerations. This solution approach is also enhanced by physics-based blocking preconditioning and multigrid algorithm for efficient inversion of preconditioners. Based on the solution approach, we have developed a reactive transport simulator named RAT. Numerical results are presented to demonstrate the efficiency and massive scalability of the simulator for reactive transport problems involving strong solution-mineral interactions and fast kinetics. It has been applied to study the highly nonlinearly coupled reactive transport system of a promising in situ environmental remediation that involves urea hydrolysis and calcium carbonate precipitation.
HyeongKae Park; Robert R. Nourgaliev; Richard C. Martineau; Dana A. Knoll
2008-09-01
We present high-order accurate spatiotemporal discretization of all-speed flow solvers using Jacobian-free Newton Krylov framework. One of the key developments in this work is the physics-based preconditioner for the all-speed flow, which makes use of traditional semi-implicit schemes. The physics-based preconditioner is developed in the primitive variable form, which allows a straightforward separation of physical phenomena. Numerical examples demonstrate that the developed preconditioner effectively reduces the number of the Krylov iterations, and the efficiency is independent of the Mach number and mesh sizes under a fixed CFL condition.
Luanjing Guo; Hai Huang; Derek Gaston; Cody Permann; David Andrs; George Redden; Chuan Lu; Don Fox; Yoshiko Fujita
2013-03-01
Modeling large multicomponent reactive transport systems in porous media is particularly challenging when the governing partial differential algebraic equations (PDAEs) are highly nonlinear and tightly coupled due to complex nonlinear reactions and strong solution-media interactions. Here we present a preconditioned Jacobian-Free Newton-Krylov (JFNK) solution approach to solve the governing PDAEs in a fully coupled and fully implicit manner. A well-known advantage of the JFNK method is that it does not require explicitly computing and storing the Jacobian matrix during Newton nonlinear iterations. Our approach further enhances the JFNK method by utilizing physics-based, block preconditioning and a multigrid algorithm for efficient inversion of the preconditioner. This preconditioning strategy accounts for self- and optionally, cross-coupling between primary variables using diagonal and off-diagonal blocks of an approximate Jacobian, respectively. Numerical results are presented demonstrating the efficiency and massive scalability of the solution strategy for reactive transport problems involving strong solution-mineral interactions and fast kinetics. We found that the physics-based, block preconditioner significantly decreases the number of linear iterations, directly reducing computational cost; and the strongly scalable algebraic multigrid algorithm for approximate inversion of the preconditioner leads to excellent parallel scaling performance.
Starke, G.
1994-12-31
For nonselfadjoint elliptic boundary value problems which are preconditioned by a substructuring method, i.e., nonoverlapping domain decomposition, the author introduces and studies the concept of subspace orthogonalization. In subspace orthogonalization variants of Krylov methods the computation of inner products and vector updates, and the storage of basis elements is restricted to a (presumably small) subspace, in this case the edge and vertex unknowns with respect to the partitioning into subdomains. The author investigates subspace orthogonalization for two specific iterative algorithms, GMRES and the full orthogonalization method (FOM). This is intended to eliminate certain drawbacks of the Arnoldi-based Krylov subspace methods mentioned above. Above all, the length of the Arnoldi recurrences grows linearly with the iteration index which is therefore restricted to the number of basis elements that can be held in memory. Restarts become necessary and this often results in much slower convergence. The subspace orthogonalization methods, in contrast, require the storage of only the edge and vertex unknowns of each basis element which means that one can iterate much longer before restarts become necessary. Moreover, the computation of inner products is also restricted to the edge and vertex points which avoids the disturbance of the computational flow associated with the solution of subdomain problems. The author views subspace orthogonalization as an alternative to restarting or truncating Krylov subspace methods for nonsymmetric linear systems of equations. Instead of shortening the recurrences, one restricts them to a subset of the unknowns which has to be carefully chosen in order to be able to extend this partial solution to the entire space. The author discusses the convergence properties of these iteration schemes and its advantages compared to restarted or truncated versions of Krylov methods applied to the full preconditioned system.
NASA Astrophysics Data System (ADS)
Viallet, M.; Goffrey, T.; Baraffe, I.; Folini, D.; Geroux, C.; Popov, M. V.; Pratt, J.; Walder, R.
2016-02-01
This work is a continuation of our efforts to develop an efficient implicit solver for multidimensional hydrodynamics for the purpose of studying important physical processes in stellar interiors, such as turbulent convection and overshooting. We present an implicit solver that results from the combination of a Jacobian-free Newton-Krylov method and a preconditioning technique tailored to the inviscid, compressible equations of stellar hydrodynamics. We assess the accuracy and performance of the solver for both 2D and 3D problems for Mach numbers down to 10-6. Although our applications concern flows in stellar interiors, the method can be applied to general advection and/or diffusion-dominated flows. The method presented in this paper opens up new avenues in 3D modeling of realistic stellar interiors allowing the study of important problems in stellar structure and evolution.
Globally convergent techniques in nonlinear Newton-Krylov
NASA Technical Reports Server (NTRS)
Brown, Peter N.; Saad, Youcef
1989-01-01
Some convergence theory is presented for nonlinear Krylov subspace methods. The basic idea of these methods is to use variants of Newton's iteration in conjunction with a Krylov subspace method for solving the Jacobian linear systems. These methods are variants of inexact Newton methods where the approximate Newton direction is taken from a subspace of small dimensions. The main focus is to analyze these methods when they are combined with global strategies such as linesearch techniques and model trust region algorithms. Most of the convergence results are formulated for projection onto general subspaces rather than just Krylov subspaces.
Polynomial preconditioning for conjugate gradient methods
Ashby, S.F.
1987-12-01
The solution of a linear system of equations, Ax = b, arises in many scientific applications. If A is large and sparse, an iterative method is required. When A is hermitian positive definite (hpd), the conjugate gradient method of Hestenes and Stiefel is popular. When A is hermitian indefinite (hid), the conjugate residual method may be used. If A is ill-conditioned, these methods may converge slowly, in which case a preconditioner is needed. In this thesis we examine the use of polynomial preconditioning in CG methods for both hermitian positive definite and indefinite matrices. Such preconditioners are easy to employ and well-suited to vector and/or parallel architectures. We first show that any CG method is characterized by three matrices: an hpd inner product matrix B, a preconditioning matrix C, and the hermitian matrix A. The resulting method, CG(B,C,A), minimizes the B-norm of the error over a Krylov subspace. We next exploit the versatility of polynomial preconditioners to design several new CG methods. To obtain an optimum preconditioner, we solve a constrained minimax approximation problem. The preconditioning polynomial, C(lambda), is optimum in that it minimizes a bound on the condition number of the preconditioned matrix, p/sub m/(A). An adaptive procedure for dynamically determining the optimum preconditioner is also discussed. Finally, in a variety of numerical experiments, conducted on a Cray X-MP/48, we demonstrate the effectiveness of polynomial preconditioning. 66 ref., 19 figs., 39 tabs.
McHugh, P.R.
1995-10-01
Fully coupled, Newton-Krylov algorithms are investigated for solving strongly coupled, nonlinear systems of partial differential equations arising in the field of computational fluid dynamics. Primitive variable forms of the steady incompressible and compressible Navier-Stokes and energy equations that describe the flow of a laminar Newtonian fluid in two-dimensions are specifically considered. Numerical solutions are obtained by first integrating over discrete finite volumes that compose the computational mesh. The resulting system of nonlinear algebraic equations are linearized using Newton`s method. Preconditioned Krylov subspace based iterative algorithms then solve these linear systems on each Newton iteration. Selected Krylov algorithms include the Arnoldi-based Generalized Minimal RESidual (GMRES) algorithm, and the Lanczos-based Conjugate Gradients Squared (CGS), Bi-CGSTAB, and Transpose-Free Quasi-Minimal Residual (TFQMR) algorithms. Both Incomplete Lower-Upper (ILU) factorization and domain-based additive and multiplicative Schwarz preconditioning strategies are studied. Numerical techniques such as mesh sequencing, adaptive damping, pseudo-transient relaxation, and parameter continuation are used to improve the solution efficiency, while algorithm implementation is simplified using a numerical Jacobian evaluation. The capabilities of standard Newton-Krylov algorithms are demonstrated via solutions to both incompressible and compressible flow problems. Incompressible flow problems include natural convection in an enclosed cavity, and mixed/forced convection past a backward facing step.
Combined incomplete LU and strongly implicit procedure preconditioning
Meese, E.A.
1996-12-31
For the solution of large sparse linear systems of equations, the Krylov-subspace methods have gained great merit. Their efficiency are, however, largely dependent upon preconditioning of the equation-system. A family of matrix factorisations often used for preconditioning, is obtained from a truncated Gaussian elimination, ILU(p). Less common, supposedly due to it`s restriction to certain sparsity patterns, is factorisations generated by the strongly implicit procedure (SIP). The ideas from ILU(p) and SIP are used in this paper to construct a generalized strongly implicit procedure, applicable to matrices with any sparsity pattern. The new algorithm has been run on some test equations, and efficiency improvements over ILU(p) was found.
Multigrid in energy preconditioner for Krylov solvers
Slaybaugh, R.N.; Evans, T.M.; Davidson, G.G.; Wilson, P.P.H.
2013-06-01
We have added a new multigrid in energy (MGE) preconditioner to the Denovo discrete-ordinates radiation transport code. This preconditioner takes advantage of a new multilevel parallel decomposition. A multigroup Krylov subspace iterative solver that is decomposed in energy as well as space-angle forms the backbone of the transport solves in Denovo. The space-angle-energy decomposition facilitates scaling to hundreds of thousands of cores. The multigrid in energy preconditioner scales well in the energy dimension and significantly reduces the number of Krylov iterations required for convergence. This preconditioner is well-suited for use with advanced eigenvalue solvers such as Rayleigh Quotient Iteration and Arnoldi.
Krylov subspace acceleration of waveform relaxation
Lumsdaine, A.; Wu, Deyun
1996-12-31
Standard solution methods for numerically solving time-dependent problems typically begin by discretizing the problem on a uniform time grid and then sequentially solving for successive time points. The initial time discretization imposes a serialization to the solution process and limits parallel speedup to the speedup available from parallelizing the problem at any given time point. This bottleneck can be circumvented by the use of waveform methods in which multiple time-points of the different components of the solution are computed independently. With the waveform approach, a problem is first spatially decomposed and distributed among the processors of a parallel machine. Each processor then solves its own time-dependent subsystem over the entire interval of interest using previous iterates from other processors as inputs. Synchronization and communication between processors take place infrequently, and communication consists of large packets of information - discretized functions of time (i.e., waveforms).
NASA Astrophysics Data System (ADS)
Jia, Jinhong; Wang, Hong
2015-10-01
Numerical methods for fractional differential equations generate full stiffness matrices, which were traditionally solved via Gaussian type direct solvers that require O (N3) of computational work and O (N2) of memory to store where N is the number of spatial grid points in the discretization. We develop a preconditioned fast Krylov subspace iterative method for the efficient and faithful solution of finite volume schemes defined on a locally refined composite mesh for fractional differential equations to resolve boundary layers of the solutions. Numerical results are presented to show the utility of the method.
Approximate inverse preconditioning of iterative methods for nonsymmetric linear systems
Benzi, M.; Tuma, M.
1996-12-31
A method for computing an incomplete factorization of the inverse of a nonsymmetric matrix A is presented. The resulting factorized sparse approximate inverse is used as a preconditioner in the iterative solution of Ax = b by Krylov subspace methods.
Portable, parallel, reusable Krylov space codes
Smith, B.; Gropp, W.
1994-12-31
Krylov space accelerators are an important component of many algorithms for the iterative solution of linear systems. Each Krylov space method has it`s own particular advantages and disadvantages, therefore it is desirable to have a variety of them available all with an identical, easy to use, interface. A common complaint application programmers have with available software libraries for the iterative solution of linear systems is that they require the programmer to use the data structures provided by the library. The library is not able to work with the data structures of the application code. Hence, application programmers find themselves constantly recoding the Krlov space algorithms. The Krylov space package (KSP) is a data-structure-neutral implementation of a variety of Krylov space methods including preconditioned conjugate gradient, GMRES, BiCG-Stab, transpose free QMR and CGS. Unlike all other software libraries for linear systems that the authors are aware of, KSP will work with any application codes data structures, in Fortran or C. Due to it`s data-structure-neutral design KSP runs unchanged on both sequential and parallel machines. KSP has been tested on workstations, the Intel i860 and Paragon, Thinking Machines CM-5 and the IBM SP1.
Block-Krylov component synthesis method for structural model reduction
NASA Technical Reports Server (NTRS)
Craig, Roy R., Jr.; Hale, Arthur L.
1988-01-01
A new analytical method is presented for generating component shape vectors, or Ritz vectors, for use in component synthesis. Based on the concept of a block-Krylov subspace, easily derived recurrence relations generate blocks of Ritz vectors for each component. The subspace spanned by the Ritz vectors is called a block-Krylov subspace. The synthesis uses the new Ritz vectors rather than component normal modes to reduce the order of large, finite-element component models. An advantage of the Ritz vectors is that they involve significantly less computation than component normal modes. Both 'free-interface' and 'fixed-interface' component models are derived. They yield block-Krylov formulations paralleling the concepts of free-interface and fixed-interface component modal synthesis. Additionally, block-Krylov reduced-order component models are shown to have special disturbability/observability properties. Consequently, the method is attractive in active structural control applications, such as large space structures. The new fixed-interface methodology is demonstrated by a numerical example. The accuracy is found to be comparable to that of fixed-interface component modal synthesis.
Preconditioned conjugate gradient methods for the Navier-Stokes equations
NASA Technical Reports Server (NTRS)
Ajmani, Kumud; Ng, Wing-Fai; Liou, Meng-Sing
1994-01-01
A preconditioned Krylov subspace method (GMRES) is used to solve the linear systems of equations formed at each time-integration step of the unsteady, two-dimensional, compressible Navier-Stokes equations of fluid flow. The Navier-Stokes equations are cast in an implicit, upwind finite-volume, flux-split formulation. Several preconditioning techniques are investigated to enhance the efficiency and convergence rate of the implicit solver based on the GMRES algorithm. The superiority of the new solver is established by comparisons with a conventional implicit solver, namely line Gauss-Seidel relaxation (LGSR). Computational test results for low-speed (incompressible flow over a backward-facing step at Mach 0.1), transonic flow (trailing edge flow in a transonic turbine cascade), and hypersonic flow (shock-on-shock interactions on a cylindrical leading edge at Mach 6.0) are presented. For the Mach 0.1 case, overall speedup factors of up to 17 (in terms of time-steps) and 15 (in terms of CPU time on a CRAY-YMP/8) are found in favor of the preconditioned GMRES solver, when compared with the LGSR solver. The corresponding speedup factors for the transonic flow case are 17 and 23, respectively. The hypersonic flow case shows slightly lower speedup factors of 9 and 13, respectively. The study of preconditioners conducted in this research reveals that a new LUSGS-type preconditioner is much more efficient than a conventional incomplete LU-type preconditioner.
Preconditioned conjugate gradient methods for the Navier-Stokes equations
Ajmani, K.; Ng, Wing Fai ); Liou, Meng Sing )
1994-01-01
A preconditioned Krylov subspace method (GMRES) is used to solve the linear systems of equations formed at each time-integration step of the unsteady, two-dimensional, compressible Navier-Stokes equations of fluid flow. The Navier-Stokes equations are cast in an implicit, upwind finite-volume, flux-split formulations. Several preconditioning techniques are investigated to enhance the efficiency and convergence rate of the implicit solver based on the GMRES algorithm. The superiority of the new solver is established by comparisons with a (LGSR). Computational test results for low-speed (incompressible flow over a backward-facing step at Mach 0.1), transonic flow (trailing edge flow in a transonic turbine cascade), and hypersonic flow (shock-on-shock interactions on a cylindrical leading edge at Mach 6.0) are presented. For the Mach 0.1 case, overall speedup factors of up to 17 (in terms of time-steps) and 15 (in terms of CPU times on a CRAY-YMP/8) are found in favor of the preconditioned GMRES solver, when compared with the LGSR solver. The corresponding speedup factors for the transonic flow cases are 17 and 23, respectively. The hypersonic flow case shows slightly lower speedup factors of 9 and 13, respectively. The study of preconditioners conducted in this research reveals that a new LUSGS-type preconditioner is much more efficient than a conventional incomplete LU-type preconditioner. 34 refs., 15 figs.
Scharz Preconditioners for Krylov Methods: Theory and Practice
Szyld, Daniel B.
2013-05-10
Several numerical methods were produced and analyzed. The main thrust of the work relates to inexact Krylov subspace methods for the solution of linear systems of equations arising from the discretization of partial di erential equa- tions. These are iterative methods, i.e., where an approximation is obtained and at each step. Usually, a matrix-vector product is needed at each iteration. In the inexact methods, this product (or the application of a preconditioner) can be done inexactly. Schwarz methods, based on domain decompositions, are excellent preconditioners for thise systems. We contributed towards their under- standing from an algebraic point of view, developed new ones, and studied their performance in the inexact setting. We also worked on combinatorial problems to help de ne the algebraic partition of the domains, with the needed overlap, as well as PDE-constraint optimization using the above-mentioned inexact Krylov subspace methods.
Newton-Krylov methods applied to nonequilibrium radiation diffusion
Knoll, D.A.; Rider, W.J.; Olsen, G.L.
1998-03-10
The authors present results of applying a matrix-free Newton-Krylov method to a nonequilibrium radiation diffusion problem. Here, there is no use of operator splitting, and Newton`s method is used to convert the nonlinearities within a time step. Since the nonlinear residual is formed, it is used to monitor convergence. It is demonstrated that a simple Picard-based linearization produces a sufficient preconditioning matrix for the Krylov method, thus elevating the need to form or store a Jacobian matrix for Newton`s method. They discuss the possibility that the Newton-Krylov approach may allow larger time steps, without loss of accuracy, as compared to an operator split approach where nonlinearities are not converged within a time step.
Accelerating molecular property calculations with nonorthonormal Krylov space methods.
Furche, Filipp; Krull, Brandon T; Nguyen, Brian D; Kwon, Jake
2016-05-01
We formulate Krylov space methods for large eigenvalue problems and linear equation systems that take advantage of decreasing residual norms to reduce the cost of matrix-vector multiplication. The residuals are used as subspace basis without prior orthonormalization, which leads to generalized eigenvalue problems or linear equation systems on the Krylov space. These nonorthonormal Krylov space (nKs) algorithms are favorable for large matrices with irregular sparsity patterns whose elements are computed on the fly, because fewer operations are necessary as the residual norm decreases as compared to the conventional method, while errors in the desired eigenpairs and solution vectors remain small. We consider real symmetric and symplectic eigenvalue problems as well as linear equation systems and Sylvester equations as they appear in configuration interaction and response theory. The nKs method can be implemented in existing electronic structure codes with minor modifications and yields speed-ups of 1.2-1.8 in typical time-dependent Hartree-Fock and density functional applications without accuracy loss. The algorithm can compute entire linear subspaces simultaneously which benefits electronic spectra and force constant calculations requiring many eigenpairs or solution vectors. The nKs approach is related to difference density methods in electronic ground state calculations and particularly efficient for integral direct computations of exchange-type contractions. By combination with resolution-of-the-identity methods for Coulomb contractions, three- to fivefold speed-ups of hybrid time-dependent density functional excited state and response calculations are achieved. PMID:27155623
Accelerating molecular property calculations with nonorthonormal Krylov space methods
NASA Astrophysics Data System (ADS)
Furche, Filipp; Krull, Brandon T.; Nguyen, Brian D.; Kwon, Jake
2016-05-01
We formulate Krylov space methods for large eigenvalue problems and linear equation systems that take advantage of decreasing residual norms to reduce the cost of matrix-vector multiplication. The residuals are used as subspace basis without prior orthonormalization, which leads to generalized eigenvalue problems or linear equation systems on the Krylov space. These nonorthonormal Krylov space (nKs) algorithms are favorable for large matrices with irregular sparsity patterns whose elements are computed on the fly, because fewer operations are necessary as the residual norm decreases as compared to the conventional method, while errors in the desired eigenpairs and solution vectors remain small. We consider real symmetric and symplectic eigenvalue problems as well as linear equation systems and Sylvester equations as they appear in configuration interaction and response theory. The nKs method can be implemented in existing electronic structure codes with minor modifications and yields speed-ups of 1.2-1.8 in typical time-dependent Hartree-Fock and density functional applications without accuracy loss. The algorithm can compute entire linear subspaces simultaneously which benefits electronic spectra and force constant calculations requiring many eigenpairs or solution vectors. The nKs approach is related to difference density methods in electronic ground state calculations and particularly efficient for integral direct computations of exchange-type contractions. By combination with resolution-of-the-identity methods for Coulomb contractions, three- to fivefold speed-ups of hybrid time-dependent density functional excited state and response calculations are achieved.
Lattice QCD computations: Recent progress with modern Krylov subspace methods
Frommer, A.
1996-12-31
Quantum chromodynamics (QCD) is the fundamental theory of the strong interaction of matter. In order to compare the theory with results from experimental physics, the theory has to be reformulated as a discrete problem of lattice gauge theory using stochastic simulations. The computational challenge consists in solving several hundreds of very large linear systems with several right hand sides. A considerable part of the world`s supercomputer time is spent in such QCD calculations. This paper presents results on solving systems for the Wilson fermions. Recent progress is reviewed on algorithms obtained in cooperation with partners from theoretical physics.
A multigrid Newton-Krylov method for flux-limited radiation diffusion
Rider, W.J.; Knoll, D.A.; Olson, G.L.
1998-09-01
The authors focus on the integration of radiation diffusion including flux-limited diffusion coefficients. The nonlinear integration is accomplished with a Newton-Krylov method preconditioned with a multigrid Picard linearization of the governing equations. They investigate the efficiency of the linear and nonlinear iterative techniques.
Simple preconditioning for time-dependent density functional perturbation theory.
Lehtovaara, Lauri; Marques, Miguel A L
2011-07-01
By far, the most common use of time-dependent density functional theory is in the linear-reponse regime, where it provides information about electronic excitations. Ideally, the linear-response equations should be solved by a method that avoids the use of the unoccupied Kohn-Sham states--such as the Sternheimer method--as this reduces the complexity and increases the precision of the calculation. However, the Sternheimer equation becomes ill-conditioned near and indefinite above the first resonant frequency, seriously hindering the use of efficient iterative solution methods. To overcome this serious limitation, and to improve the general convergence properties of the iterative techniques, we propose a simple preconditioning strategy. In our method, the Sternheimer equation is solved directly as a linear equation using an iterative Krylov subspace method, i.e., no self-consistent cycle is required. Furthermore, the preconditioner uses the information of just a few unoccupied states and requires simple and minimal modifications to existing implementations. In this way, convergence can be reached faster and in a considerably wider frequency range than the traditional approach. PMID:21744884
Accelerating molecular property calculations with nonorthonormal Krylov space methods
Furche, Filipp; Krull, Brandon T.; Nguyen, Brian D.; Kwon, Jake
2016-05-03
Here, we formulate Krylov space methods for large eigenvalue problems and linear equation systems that take advantage of decreasing residual norms to reduce the cost of matrix-vector multiplication. The residuals are used as subspace basis without prior orthonormalization, which leads to generalized eigenvalue problems or linear equation systems on the Krylov space. These nonorthonormal Krylov space (nKs) algorithms are favorable for large matrices with irregular sparsity patterns whose elements are computed on the fly, because fewer operations are necessary as the residual norm decreases as compared to the conventional method, while errors in the desired eigenpairs and solution vectors remainmore » small. We consider real symmetric and symplectic eigenvalue problems as well as linear equation systems and Sylvester equations as they appear in configuration interaction and response theory. The nKs method can be implemented in existing electronic structure codes with minor modifications and yields speed-ups of 1.2-1.8 in typical time-dependent Hartree-Fock and density functional applications without accuracy loss. The algorithm can compute entire linear subspaces simultaneously which benefits electronic spectra and force constant calculations requiring many eigenpairs or solution vectors. The nKs approach is related to difference density methods in electronic ground state calculations and particularly efficient for integral direct computations of exchange-type contractions. By combination with resolution-of-the-identity methods for Coulomb contractions, three- to fivefold speed-ups of hybrid time-dependent density functional excited state and response calculations are achieved.« less
Conformal mapping and convergence of Krylov iterations
Driscoll, T.A.; Trefethen, L.N.
1994-12-31
Connections between conformal mapping and matrix iterations have been known for many years. The idea underlying these connections is as follows. Suppose the spectrum of a matrix or operator A is contained in a Jordan region E in the complex plane with 0 not an element of E. Let {phi}(z) denote a conformal map of the exterior of E onto the exterior of the unit disk, with {phi}{infinity} = {infinity}. Then 1/{vert_bar}{phi}(0){vert_bar} is an upper bound for the optimal asymptotic convergence factor of any Krylov subspace iteration. This idea can be made precise in various ways, depending on the matrix iterations, on whether A is finite or infinite dimensional, and on what bounds are assumed on the non-normality of A. This paper explores these connections for a variety of matrix examples, making use of a new MATLAB Schwarz-Christoffel Mapping Toolbox developed by the first author. Unlike the earlier Fortran Schwarz-Christoffel package SCPACK, the new toolbox computes exterior as well as interior Schwarz-Christoffel maps, making it easy to experiment with spectra that are not necessarily symmetric about an axis.
Application of nonlinear Krylov acceleration to radiative transfer problems
Till, A. T.; Adams, M. L.; Morel, J. E.
2013-07-01
The iterative solution technique used for radiative transfer is normally nested, with outer thermal iterations and inner transport iterations. We implement a nonlinear Krylov acceleration (NKA) method in the PDT code for radiative transfer problems that breaks nesting, resulting in more thermal iterations but significantly fewer total inner transport iterations. Using the metric of total inner transport iterations, we investigate a crooked-pipe-like problem and a pseudo-shock-tube problem. Using only sweep preconditioning, we compare NKA against a typical inner / outer method employing GMRES / Newton and find NKA to be comparable or superior. Finally, we demonstrate the efficacy of applying diffusion-based preconditioning to grey problems in conjunction with NKA. (authors)
Krylov methods for compressible flows
NASA Technical Reports Server (NTRS)
Tidriri, M. D.
1995-01-01
We investigate the application of Krylov methods to compressible flows, and the effect of implicit boundary conditions on the implicit solution of nonlinear problems. Two defect-correction procedures, namely, approximate factorization (AF) for structured grids and ILU/GMRES for general grids, are considered. Also considered here are Newton-Krylov matrix-free methods that we combined with the use of mixed discretization schemes in the implicitly defined Jacobian and its preconditioner. Numerical experiments that show the performance of our approaches are then presented.
Harris, D B
2006-07-11
Broadband subspace detectors are introduced for seismological applications that require the detection of repetitive sources that produce similar, yet significantly variable seismic signals. Like correlation detectors, of which they are a generalization, subspace detectors often permit remarkably sensitive detection of small events. The subspace detector derives its name from the fact that it projects a sliding window of data drawn from a continuous stream onto a vector signal subspace spanning the collection of signals expected to be generated by a particular source. Empirical procedures are presented for designing subspaces from clusters of events characterizing a source. Furthermore, a solution is presented for the problem of selecting the dimension of the subspace to maximize the probability of detecting repetitive events at a fixed false alarm rate. An example illustrates subspace design and detection using events in the 2002 San Ramon, California earthquake swarm.
Improvements in Block-Krylov Ritz Vectors and the Boundary Flexibility Method of Component Synthesis
NASA Technical Reports Server (NTRS)
Carney, Kelly Scott
1997-01-01
A method of dynamic substructuring is presented which utilizes a set of static Ritz vectors as a replacement for normal eigenvectors in component mode synthesis. This set of Ritz vectors is generated in a recurrence relationship, proposed by Wilson, which has the form of a block-Krylov subspace. The initial seed to the recurrence algorithm is based upon the boundary flexibility vectors of the component. Improvements have been made in the formulation of the initial seed to the Krylov sequence, through the use of block-filtering. A method to shift the Krylov sequence to create Ritz vectors that will represent the dynamic behavior of the component at target frequencies, the target frequency being determined by the applied forcing functions, has been developed. A method to terminate the Krylov sequence has also been developed. Various orthonormalization schemes have been developed and evaluated, including the Cholesky/QR method. Several auxiliary theorems and proofs which illustrate issues in component mode synthesis and loss of orthogonality in the Krylov sequence have also been presented. The resulting methodology is applicable to both fixed and free- interface boundary components, and results in a general component model appropriate for any type of dynamic analysis. The accuracy is found to be comparable to that of component synthesis based upon normal modes, using fewer generalized coordinates. In addition, the block-Krylov recurrence algorithm is a series of static solutions and so requires significantly less computation than solving the normal eigenspace problem. The requirement for less vectors to form the component, coupled with the lower computational expense of calculating these Ritz vectors, combine to create a method more efficient than traditional component mode synthesis.
NASA Astrophysics Data System (ADS)
Bisetti, Fabrizio
2012-06-01
Recent trends in hydrocarbon fuel research indicate that the number of species and reactions in chemical kinetic mechanisms is rapidly increasing in an effort to provide predictive capabilities for fuels of practical interest. In order to cope with the computational cost associated with the time integration of stiff, large chemical systems, a novel approach is proposed. The approach combines an exponential integrator and Krylov subspace approximations to the exponential function of the Jacobian matrix. The components of the approach are described in detail and applied to the ignition of stoichiometric methane-air and iso-octane-air mixtures, here described by two widely adopted chemical kinetic mechanisms. The approach is found to be robust even at relatively large time steps and the global error displays a nominal third-order convergence. The performance of the approach is improved by utilising an adaptive algorithm for the selection of the Krylov subspace size, which guarantees an approximation to the matrix exponential within user-defined error tolerance. The Krylov projection of the Jacobian matrix onto a low-dimensional space is interpreted as a local model reduction with a well-defined error control strategy. Finally, the performance of the approach is discussed with regard to the optimal selection of the parameters governing the accuracy of its individual components.
Projection preconditioning for Lanczos-type methods
Bielawski, S.S.; Mulyarchik, S.G.; Popov, A.V.
1996-12-31
We show how auxiliary subspaces and related projectors may be used for preconditioning nonsymmetric system of linear equations. It is shown that preconditioned in such a way (or projected) system is better conditioned than original system (at least if the coefficient matrix of the system to be solved is symmetrizable). Two approaches for solving projected system are outlined. The first one implies straightforward computation of the projected matrix and consequent using some direct or iterative method. The second approach is the projection preconditioning of conjugate gradient-type solver. The latter approach is developed here in context with biconjugate gradient iteration and some related Lanczos-type algorithms. Some possible particular choices of auxiliary subspaces are discussed. It is shown that one of them is equivalent to using colorings. Some results of numerical experiments are reported.
NASA Astrophysics Data System (ADS)
Koldan, Jelena; Puzyrev, Vladimir; de la Puente, Josep; Houzeaux, Guillaume; Cela, José María
2014-06-01
We present an elaborate preconditioning scheme for Krylov subspace methods which has been developed to improve the performance and reduce the execution time of parallel node-based finite-element (FE) solvers for 3-D electromagnetic (EM) numerical modelling in exploration geophysics. This new preconditioner is based on algebraic multigrid (AMG) that uses different basic relaxation methods, such as Jacobi, symmetric successive over-relaxation (SSOR) and Gauss-Seidel, as smoothers and the wave front algorithm to create groups, which are used for a coarse-level generation. We have implemented and tested this new preconditioner within our parallel nodal FE solver for 3-D forward problems in EM induction geophysics. We have performed series of experiments for several models with different conductivity structures and characteristics to test the performance of our AMG preconditioning technique when combined with biconjugate gradient stabilized method. The results have shown that, the more challenging the problem is in terms of conductivity contrasts, ratio between the sizes of grid elements and/or frequency, the more benefit is obtained by using this preconditioner. Compared to other preconditioning schemes, such as diagonal, SSOR and truncated approximate inverse, the AMG preconditioner greatly improves the convergence of the iterative solver for all tested models. Also, when it comes to cases in which other preconditioners succeed to converge to a desired precision, AMG is able to considerably reduce the total execution time of the forward-problem code-up to an order of magnitude. Furthermore, the tests have confirmed that our AMG scheme ensures grid-independent rate of convergence, as well as improvement in convergence regardless of how big local mesh refinements are. In addition, AMG is designed to be a black-box preconditioner, which makes it easy to use and combine with different iterative methods. Finally, it has proved to be very practical and efficient in the
Implementation of the block-Krylov boundary flexibility method of component synthesis
NASA Technical Reports Server (NTRS)
Carney, Kelly S.; Abdallah, Ayman A.; Hucklebridge, Arthur A.
1993-01-01
A method of dynamic substructuring is presented which utilizes a set of static Ritz vectors as a replacement for normal eigenvectors in component mode synthesis. This set of Ritz vectors is generated in a recurrence relationship, which has the form of a block-Krylov subspace. The initial seed to the recurrence algorithm is based on the boundary flexibility vectors of the component. This algorithm is not load-dependent, is applicable to both fixed and free-interface boundary components, and results in a general component model appropriate for any type of dynamic analysis. This methodology was implemented in the MSC/NASTRAN normal modes solution sequence using DMAP. The accuracy is found to be comparable to that of component synthesis based upon normal modes. The block-Krylov recurrence algorithm is a series of static solutions and so requires significantly less computation than solving the normal eigenspace problem.
Implementation of the block-Krylov boundary flexibility method of component synthesis
NASA Astrophysics Data System (ADS)
Carney, Kelly S.; Abdallah, Ayman A.; Hucklebridge, Arthur A.
1993-05-01
A method of dynamic substructuring is presented which utilizes a set of static Ritz vectors as a replacement for normal eigenvectors in component mode synthesis. This set of Ritz vectors is generated in a recurrence relationship, which has the form of a block-Krylov subspace. The initial seed to the recurrence algorithm is based on the boundary flexibility vectors of the component. This algorithm is not load-dependent, is applicable to both fixed and free-interface boundary components, and results in a general component model appropriate for any type of dynamic analysis. This methodology was implemented in the MSC/NASTRAN normal modes solution sequence using DMAP. The accuracy is found to be comparable to that of component synthesis based upon normal modes. The block-Krylov recurrence algorithm is a series of static solutions and so requires significantly less computation than solving the normal eigenspace problem.
Newton-Raphson preconditioner for Krylov type solvers on GPU devices.
Kushida, Noriyuki
2016-01-01
A new Newton-Raphson method based preconditioner for Krylov type linear equation solvers for GPGPU is developed, and the performance is investigated. Conventional preconditioners improve the convergence of Krylov type solvers, and perform well on CPUs. However, they do not perform well on GPGPUs, because of the complexity of implementing powerful preconditioners. The developed preconditioner is based on the BFGS Hessian matrix approximation technique, which is well known as a robust and fast nonlinear equation solver. Because the Hessian matrix in the BFGS represents the coefficient matrix of a system of linear equations in some sense, the approximated Hessian matrix can be a preconditioner. On the other hand, BFGS is required to store dense matrices and to invert them, which should be avoided on modern computers and supercomputers. To overcome these disadvantages, we therefore introduce a limited memory BFGS, which requires less memory space and less computational effort than the BFGS. In addition, a limited memory BFGS can be implemented with BLAS libraries, which are well optimized for target architectures. There are advantages and disadvantages to the Hessian matrix approximation becoming better as the Krylov solver iteration continues. The preconditioning matrix varies through Krylov solver iterations, and only flexible Krylov solvers can work well with the developed preconditioner. The GCR method, which is a flexible Krylov solver, is employed because of the prevalence of GCR as a Krylov solver with a variable preconditioner. As a result of the performance investigation, the new preconditioner indicates the following benefits: (1) The new preconditioner is robust; i.e., it converges while conventional preconditioners (the diagonal scaling, and the SSOR preconditioners) fail. (2) In the best case scenarios, it is over 10 times faster than conventional preconditioners on a CPU. (3) Because it requries only simple operations, it performs well on a GPGPU. In
Left and right preconditioning for electrical impedance tomography with structural information
NASA Astrophysics Data System (ADS)
Calvetti, Daniela; McGivney, Debra; Somersalo, Erkki
2012-05-01
A common problem in computational inverse problems is to find an efficient way of solving linear or nonlinear least-squares problems. For large-scale problems, iterative solvers are the method of choice for solving the associated linear systems, and for nonlinear problems, an additional effective local linearization method is required. In this paper, we discuss an efficient preconditioning scheme for Krylov subspace methods, based on the Bayesian analysis of the inverse problem. The model problem to which we apply this methodology is electrical impedance tomography (EIT) augmented with prior information coming from a complementary modality, such as x-ray imaging. The particular geometry considered here models the x-ray-guided EIT for breast imaging. The interest in applying EIT concurrently with x-ray breast imaging arises from the experimental observation that the impedivity spectra of certain types of malignant and benign tissues differ significantly from each other, thus offering a possibility of diagnosis without more invasive tissue sampling. After setting up the EIT inverse problem within a Bayesian framework, we present an inner and outer iteration scheme for computing a maximum a posteriori estimate. The prior covariance provides a right preconditioner and the modeling error covariance provides a left preconditioner for the iterative method used to solve the linear least-squares problem at each outer iteration of the optimization problem. Moreover, the stopping criterion for the inner iterations is coupled with the progress of the solution of the outer iteration. Besides the preconditioning scheme, the computational efficiency relies on a very efficient method to compute the Jacobian, obtained by carefully organizing the forward computation. Computed examples illustrate the robustness and computational efficiency of the proposed algorithm.
Acceleration of k-Eigenvalue / Criticality Calculations using the Jacobian-Free Newton-Krylov Method
Dana Knoll; HyeongKae Park; Chris Newman
2011-02-01
We present a new approach for the $k$--eigenvalue problem using a combination of classical power iteration and the Jacobian--free Newton--Krylov method (JFNK). The method poses the $k$--eigenvalue problem as a fully coupled nonlinear system, which is solved by JFNK with an effective block preconditioning consisting of the power iteration and algebraic multigrid. We demonstrate effectiveness and algorithmic scalability of the method on a 1-D, one group problem and two 2-D two group problems and provide comparison to other efforts using silmilar algorithmic approaches.
Efficient solution of parabolic equations by Krylov approximation methods
NASA Technical Reports Server (NTRS)
Gallopoulos, E.; Saad, Y.
1990-01-01
Numerical techniques for solving parabolic equations by the method of lines is addressed. The main motivation for the proposed approach is the possibility of exploiting a high degree of parallelism in a simple manner. The basic idea of the method is to approximate the action of the evolution operator on a given state vector by means of a projection process onto a Krylov subspace. Thus, the resulting approximation consists of applying an evolution operator of a very small dimension to a known vector which is, in turn, computed accurately by exploiting well-known rational approximations to the exponential. Because the rational approximation is only applied to a small matrix, the only operations required with the original large matrix are matrix-by-vector multiplications, and as a result the algorithm can easily be parallelized and vectorized. Some relevant approximation and stability issues are discussed. We present some numerical experiments with the method and compare its performance with a few explicit and implicit algorithms.
NASA Astrophysics Data System (ADS)
Aliaga, José I.; Alonso, Pedro; Badía, José M.; Chacón, Pablo; Davidović, Davor; López-Blanco, José R.; Quintana-Ortí, Enrique S.
2016-03-01
We introduce a new iterative Krylov subspace-based eigensolver for the simulation of macromolecular motions on desktop multithreaded platforms equipped with multicore processors and, possibly, a graphics accelerator (GPU). The method consists of two stages, with the original problem first reduced into a simpler band-structured form by means of a high-performance compute-intensive procedure. This is followed by a memory-intensive but low-cost Krylov iteration, which is off-loaded to be computed on the GPU by means of an efficient data-parallel kernel. The experimental results reveal the performance of the new eigensolver. Concretely, when applied to the simulation of macromolecules with a few thousands degrees of freedom and the number of eigenpairs to be computed is small to moderate, the new solver outperforms other methods implemented as part of high-performance numerical linear algebra packages for multithreaded architectures.
An Inexact Newton–Krylov Algorithm for Constrained Diffeomorphic Image Registration*
Mang, Andreas; Biros, George
2016-01-01
We propose numerical algorithms for solving large deformation diffeomorphic image registration problems. We formulate the nonrigid image registration problem as a problem of optimal control. This leads to an infinite-dimensional partial differential equation (PDE) constrained optimization problem. The PDE constraint consists, in its simplest form, of a hyperbolic transport equation for the evolution of the image intensity. The control variable is the velocity field. Tikhonov regularization on the control ensures well-posedness. We consider standard smoothness regularization based on H1- or H2-seminorms. We augment this regularization scheme with a constraint on the divergence of the velocity field (control variable) rendering the deformation incompressible (Stokes regularization scheme) and thus ensuring that the determinant of the deformation gradient is equal to one, up to the numerical error. We use a Fourier pseudospectral discretization in space and a Chebyshev pseudospectral discretization in time. The latter allows us to reduce the number of unknowns and enables the time-adaptive inversion for nonstationary velocity fields. We use a preconditioned, globalized, matrix-free, inexact Newton–Krylov method for numerical optimization. A parameter continuation is designed to estimate an optimal regularization parameter. Regularity is ensured by controlling the geometric properties of the deformation field. Overall, we arrive at a black-box solver that exploits computational tools that are precisely tailored for solving the optimality system. We study spectral properties of the Hessian, grid convergence, numerical accuracy, computational efficiency, and deformation regularity of our scheme. We compare the designed Newton–Krylov methods with a globalized Picard method (preconditioned gradient descent). We study the influence of a varying number of unknowns in time. The reported results demonstrate excellent numerical accuracy, guaranteed local deformation
Notes on Newton-Krylov based Incompressible Flow Projection Solver
Robert Nourgaliev; Mark Christon; J. Bakosi
2012-09-01
The purpose of the present document is to formulate Jacobian-free Newton-Krylov algorithm for approximate projection method used in Hydra-TH code. Hydra-TH is developed by Los Alamos National Laboratory (LANL) under the auspices of the Consortium for Advanced Simulation of Light-Water Reactors (CASL) for thermal-hydraulics applications ranging from grid-to-rod fretting (GTRF) to multiphase flow subcooled boiling. Currently, Hydra-TH is based on the semi-implicit projection method, which provides an excellent platform for simulation of transient single-phase thermalhydraulics problems. This algorithm however is not efficient when applied for very slow or steady-state problems, as well as for highly nonlinear multiphase problems relevant to nuclear reactor thermalhydraulics with boiling and condensation. These applications require fully-implicit tightly-coupling algorithms. The major technical contribution of the present report is the formulation of fully-implicit projection algorithm which will fulfill this purpose. This includes the definition of non-linear residuals used for GMRES-based linear iterations, as well as physics-based preconditioning techniques.
Newton-Krylov-Schwarz methods in unstructured grid Euler flow
Keyes, D.E.
1996-12-31
Newton-Krylov methods and Krylov-Schwarz (domain decomposition) methods have begun to become established in computational fluid dynamics (CFD) over the past decade. The former employ a Krylov method inside of Newton`s method in a Jacobian-free manner, through directional differencing. The latter employ an overlapping Schwarz domain decomposition to derive a preconditioner for the Krylov accelerator that relies primarily on local information, for data-parallel concurrency. They may be composed as Newton-Krylov-Schwarz (NKS) methods, which seem particularly well suited for solving nonlinear elliptic systems in high-latency, distributed-memory environments. We give a brief description of this family of algorithms, with an emphasis on domain decomposition iterative aspects. We then describe numerical simulations with Newton-Krylov-Schwarz methods on an aerodynamic application emphasizing comparisons with a standard defect-correction approach and subdomain preconditioner consistency.
Newton-Krylov-Schwarz: An implicit solver for CFD
NASA Technical Reports Server (NTRS)
Cai, Xiao-Chuan; Keyes, David E.; Venkatakrishnan, V.
1995-01-01
Newton-Krylov methods and Krylov-Schwarz (domain decomposition) methods have begun to become established in computational fluid dynamics (CFD) over the past decade. The former employ a Krylov method inside of Newton's method in a Jacobian-free manner, through directional differencing. The latter employ an overlapping Schwarz domain decomposition to derive a preconditioner for the Krylov accelerator that relies primarily on local information, for data-parallel concurrency. They may be composed as Newton-Krylov-Schwarz (NKS) methods, which seem particularly well suited for solving nonlinear elliptic systems in high-latency, distributed-memory environments. We give a brief description of this family of algorithms, with an emphasis on domain decomposition iterative aspects. We then describe numerical simulations with Newton-Krylov-Schwarz methods on aerodynamics applications emphasizing comparisons with a standard defect-correction approach, subdomain preconditioner consistency, subdomain preconditioner quality, and the effect of a coarse grid.
Texture Representations Using Subspace Embeddings
Yang, Xiaodong; Tian, YingLi
2013-01-01
In this paper, we propose a texture representation framework to map local texture patches into a low-dimensional texture subspace. In natural texture images, textons are entangled with multiple factors, such as rotation, scaling, viewpoint variation, illumination change, and non-rigid surface deformation. Mapping local texture patches into a low-dimensional subspace can alleviate or eliminate these undesired variation factors resulting from both geometric and photometric transformations. We observe that texture representations based on subspace embeddings have strong resistance to image deformations, meanwhile, are more distinctive and more compact than traditional representations. We investigate both linear and non-linear embedding methods including Principle Component Analysis (PCA), Linear Discriminant Analysis (LDA), and Locality Preserving Projections (LPP) to compute the essential texture subspace. The experiments in the context of texture classification on benchmark datasets demonstrate that the proposed subspace embedding representations achieve the state-of-the-art results while with much fewer feature dimensions. PMID:23710105
Texture Representations Using Subspace Embeddings.
Yang, Xiaodong; Tian, Yingli
2013-07-15
In this paper, we propose a texture representation framework to map local texture patches into a low-dimensional texture subspace. In natural texture images, textons are entangled with multiple factors, such as rotation, scaling, viewpoint variation, illumination change, and non-rigid surface deformation. Mapping local texture patches into a low-dimensional subspace can alleviate or eliminate these undesired variation factors resulting from both geometric and photometric transformations. We observe that texture representations based on subspace embeddings have strong resistance to image deformations, meanwhile, are more distinctive and more compact than traditional representations. We investigate both linear and non-linear embedding methods including Principle Component Analysis (PCA), Linear Discriminant Analysis (LDA), and Locality Preserving Projections (LPP) to compute the essential texture subspace. The experiments in the context of texture classification on benchmark datasets demonstrate that the proposed subspace embedding representations achieve the state-of-the-art results while with much fewer feature dimensions. PMID:23710105
Nonlinear Krylov acceleration of reacting flow codes
Kumar, S.; Rawat, R.; Smith, P.; Pernice, M.
1996-12-31
We are working on computational simulations of three-dimensional reactive flows in applications encompassing a broad range of chemical engineering problems. Examples of such processes are coal (pulverized and fluidized bed) and gas combustion, petroleum processing (cracking), and metallurgical operations such as smelting. These simulations involve an interplay of various physical and chemical factors such as fluid dynamics with turbulence, convective and radiative heat transfer, multiphase effects such as fluid-particle and particle-particle interactions, and chemical reaction. The governing equations resulting from modeling these processes are highly nonlinear and strongly coupled, thereby rendering their solution by traditional iterative methods (such as nonlinear line Gauss-Seidel methods) very difficult and sometimes impossible. Hence we are exploring the use of nonlinear Krylov techniques (such as CMRES and Bi-CGSTAB) to accelerate and stabilize the existing solver. This strategy allows us to take advantage of the problem-definition capabilities of the existing solver. The overall approach amounts to using the SIMPLE (Semi-Implicit Method for Pressure-Linked Equations) method and its variants as nonlinear preconditioners for the nonlinear Krylov method. We have also adapted a backtracking approach for inexact Newton methods to damp the Newton step in the nonlinear Krylov method. This will be a report on work in progress. Preliminary results with nonlinear GMRES have been very encouraging: in many cases the number of line Gauss-Seidel sweeps has been reduced by about a factor of 5, and increased robustness of the underlying solver has also been observed.
NASA Astrophysics Data System (ADS)
Jiang, Tian; Zhang, Yong-Tao
2016-04-01
Implicit integration factor (IIF) methods were developed in the literature for solving time-dependent stiff partial differential equations (PDEs). Recently, IIF methods were combined with weighted essentially non-oscillatory (WENO) schemes in Jiang and Zhang (2013) [19] to efficiently solve stiff nonlinear advection-diffusion-reaction equations. The methods can be designed for arbitrary order of accuracy. The stiffness of the system is resolved well and the methods are stable by using time step sizes which are just determined by the non-stiff hyperbolic part of the system. To efficiently calculate large matrix exponentials, Krylov subspace approximation is directly applied to the implicit integration factor (IIF) methods. So far, the IIF methods developed in the literature are multistep methods. In this paper, we develop Krylov single-step IIF-WENO methods for solving stiff advection-diffusion-reaction equations. The methods are designed carefully to avoid generating positive exponentials in the matrix exponentials, which is necessary for the stability of the schemes. We analyze the stability and truncation errors of the single-step IIF schemes. Numerical examples of both scalar equations and systems are shown to demonstrate the accuracy, efficiency and robustness of the new methods.
Unsupervised Discovery of Subspace Trends.
Xu, Yan; Qiu, Peng; Roysam, Badrinath
2015-10-01
This paper presents unsupervised algorithms for discovering previously unknown subspace trends in high-dimensional data sets without the benefit of prior information. A subspace trend is a sustained pattern of gradual/progressive changes within an unknown subset of feature dimensions. A fundamental challenge to subspace trend discovery is the presence of irrelevant data dimensions, noise, outliers, and confusion from multiple subspace trends driven by independent factors that are mixed in with each other. These factors can obscure the trends in conventional dimension reduction & projection based data visualizations. To overcome these limitations, we propose a novel graph-theoretic neighborhood similarity measure for detecting concordant progressive changes across data dimensions. Using this measure, we present an unsupervised algorithm for trend-relevant feature selection, subspace trend discovery, quantification of trend strength, and validation. Our method successfully identified verifiable subspace trends in diverse synthetic and real-world biomedical datasets. Visualizations derived from the selected trend-relevant features revealed biologically meaningful hidden subspace trend(s) that were obscured by irrelevant features and noise. Although our examples are drawn from the biological domain, the proposed algorithm is broadly applicable to exploratory analysis of high-dimensional data including visualization, hypothesis generation, knowledge discovery, and prediction in diverse other applications. PMID:26353189
A compressible Navier-Stokes flow solver using the Newton-Krylov method on unstructured grids
NASA Astrophysics Data System (ADS)
Wong, Peterson
A Newton-Krylov algorithm is presented for the compressible Navier-Stokes equations on hybrid unstructured grids. The Spalart-Allmaras turbulence model is used for turbulent flows. The spatial discretization is based on a finite-volume matrix dissipation scheme. A preconditioned matrix-free generalized minimal residual method is used to solve the linear system that arises in the Newton iterations. The incomplete lower-upper factorization based on an approximate Jacobian is used as the preconditioner after applying the reverse Cuthill-McKee reordering. Various aspects of the Newton-Krylov algorithm are studied to improve efficiency and reliability. The inexact Newton method is studied to avoid over-solving of the linear system to reduce computational cost. The ILU(1) approach is selected in three dimensions, based on a comparison among various preconditioners. Approximate viscous formulations involving only the nearest neighboring terms are studied to reduce the cost of preconditioning. The resulting preconditioners are found to be effective and provide Newton-type convergence. Scaling of the linear system is studied to improve convergence of the inexact matrix-free approach. Numerical studies are performed for two-dimensional cases as well as flows over the ONERA M6 wing and the DLR-F6 wing-body configuration. A ten-order-of-magnitude residual reduction can be obtained with a computing cost equivalent to 4,000 residual function evaluations for two-dimensional cases, while the same convergence can be obtained in 5,500 and 8,000 function evaluations for the wing and wing-body configuration, respectively, on grids with a half million nodes.
Covariance Modifications to Subspace Bases
Harris, D B
2008-11-19
Adaptive signal processing algorithms that rely upon representations of signal and noise subspaces often require updates to those representations when new data become available. Subspace representations frequently are estimated from available data with singular value (SVD) decompositions. Subspace updates require modifications to these decompositions. Updates can be performed inexpensively provided they are low-rank. A substantial literature on SVD updates exists, frequently focusing on rank-1 updates (see e.g. [Karasalo, 1986; Comon and Golub, 1990, Badeau, 2004]). In these methods, data matrices are modified by addition or deletion of a row or column, or data covariance matrices are modified by addition of the outer product of a new vector. A recent paper by Brand [2006] provides a general and efficient method for arbitrary rank updates to an SVD. The purpose of this note is to describe a closely-related method for applications where right singular vectors are not required. This note also describes the SVD updates to a particular scenario of interest in seismic array signal processing. The particular application involve updating the wideband subspace representation used in seismic subspace detectors [Harris, 2006]. These subspace detectors generalize waveform correlation algorithms to detect signals that lie in a subspace of waveforms of dimension d {ge} 1. They potentially are of interest because they extend the range of waveform variation over which these sensitive detectors apply. Subspace detectors operate by projecting waveform data from a detection window into a subspace specified by a collection of orthonormal waveform basis vectors (referred to as the template). Subspace templates are constructed from a suite of normalized, aligned master event waveforms that may be acquired by a single sensor, a three-component sensor, an array of such sensors or a sensor network. The template design process entails constructing a data matrix whose columns contain the
Some experiences with Krylov vectors and Lanczos vectors
NASA Technical Reports Server (NTRS)
Craig, Roy R., Jr.; Su, Tzu-Jeng; Kim, Hyoung M.
1993-01-01
This paper illustrates the use of Krylov vectors and Lanczos vectors for reduced-order modeling in structural dynamics and for control of flexible structures. Krylov vectors and Lanczos vectors are defined and illustrated, and several applications that have been under study at The University of Texas at Austin are reviewed: model reduction for undamped structural dynamics systems, component mode synthesis using Krylov vectors, model reduction of damped structural dynamics systems, and one-sided and two-sided unsymmetric block-Lanczos model-reduction algorithms.
Fattebert, J
2008-07-29
We describe an iterative algorithm to solve electronic structure problems in Density Functional Theory. The approach is presented as a Subspace Accelerated Inexact Newton (SAIN) solver for the non-linear Kohn-Sham equations. It is related to a class of iterative algorithms known as RMM-DIIS in the electronic structure community. The method is illustrated with examples of real applications using a finite difference discretization and multigrid preconditioning.
Higher order stationary subspace analysis
NASA Astrophysics Data System (ADS)
Panknin, Danny; von Bünau, Paul; Kawanabe, Motoaki; Meinecke, Frank C.; Müller, Klaus-Robert
2016-03-01
Non-stationarity in data is an ubiquitous problem in signal processing. The recent stationary subspace analysis procedure (SSA) has enabled to decompose such data into a stationary subspace and a non-stationary part respectively. Algorithmically only weak non- stationarities could be tackled by SSA. The present paper takes the conceptual step generalizing from the use of first and second moments as in SSA to higher order moments, thus defining the proposed higher order stationary subspace analysis procedure (HOSSA). The paper derives the novel procedure and shows simulations. An obvious trade-off between the necessity of estimating higher moments and the accuracy and robustness with which they can be estimated is observed. In an ideal setting of plenty of data where higher moment information is dominating our novel approach can win against standard SSA. However, with limited data, even though higher moments actually dominate the underlying data, still SSA may arrive on par.
Molecular mechanism of preconditioning.
Das, Manika; Das, Dipak K
2008-04-01
During the last 20 years, since the appearance of the first publication on ischemic preconditioning (PC), our knowledge of this phenomenon has increased exponentially. PC is defined as an increased tolerance to ischemia and reperfusion induced by previous sublethal period ischemia. This is the most powerful mechanism known to date for limiting the infract size. This adaptation occurs in a biphasic pattern (i) early preconditioning (lasts for 2-3 h) and (ii) late preconditioning (starting at 24 h lasting until 72-96 h after initial ischemia). Early preconditioning is more potent than delayed preconditioning in reducing infract size. Late preconditioning attenuates myocardial stunning and requires genomic activation with de novo protein synthesis. Early preconditioning depends on adenosine, opioids and to a lesser degree, on bradykinin and prostaglandins, released during ischemia. These molecules activate G-protein-coupled receptor, initiate activation of K(ATP) channel and generate oxygen-free radicals, and stimulate a series of protein kinases, which include protein kinase C, tyrosine kinase, and members of MAP kinase family. Late preconditioning is triggered by a similar sequence of events, but in addition essentially depends on newly synthesized proteins, which comprise iNOS, COX-2, manganese superoxide dismutase, and possibly heat shock proteins. The final mechanism of PC is still not very clear. The present review focuses on the possible role signaling molecules that regulate cardiomyocyte life and death during ischemia and reperfusion. PMID:18344203
A Parallel Newton-Krylov-Schur Algorithm for the Reynolds-Averaged Navier-Stokes Equations
NASA Astrophysics Data System (ADS)
Osusky, Michal
Aerodynamic shape optimization and multidisciplinary optimization algorithms have the potential not only to improve conventional aircraft, but also to enable the design of novel configurations. By their very nature, these algorithms generate and analyze a large number of unique shapes, resulting in high computational costs. In order to improve their efficiency and enable their use in the early stages of the design process, a fast and robust flow solution algorithm is necessary. This thesis presents an efficient parallel Newton-Krylov-Schur flow solution algorithm for the three-dimensional Navier-Stokes equations coupled with the Spalart-Allmaras one-equation turbulence model. The algorithm employs second-order summation-by-parts (SBP) operators on multi-block structured grids with simultaneous approximation terms (SATs) to enforce block interface coupling and boundary conditions. The discrete equations are solved iteratively with an inexact-Newton method, while the linear system at each Newton iteration is solved using the flexible Krylov subspace iterative method GMRES with an approximate-Schur parallel preconditioner. The algorithm is thoroughly verified and validated, highlighting the correspondence of the current algorithm with several established flow solvers. The solution for a transonic flow over a wing on a mesh of medium density (15 million nodes) shows good agreement with experimental results. Using 128 processors, deep convergence is obtained in under 90 minutes. The solution of transonic flow over the Common Research Model wing-body geometry with grids with up to 150 million nodes exhibits the expected grid convergence behavior. This case was completed as part of the Fifth AIAA Drag Prediction Workshop, with the algorithm producing solutions that compare favourably with several widely used flow solvers. The algorithm is shown to scale well on over 6000 processors. The results demonstrate the effectiveness of the SBP-SAT spatial discretization, which can
NASA Astrophysics Data System (ADS)
Asgharzadeh, Hafez; Borazjani, Iman
2014-11-01
Time step-size restrictions and low convergence rates are major bottle necks for implicit solution of the Navier-Stokes in simulations involving complex geometries with moving boundaries. Newton-Krylov method (NKM) is a combination of a Newton-type method for super-linearly convergent solution of nonlinear equations and Krylov subspace methods for solving the Newton correction equations, which can theoretically address both bottle necks. The efficiency of this method vastly depends on the Jacobian forming scheme e.g. automatic differentiation is very expensive and Jacobian-free methods slow down as the mesh is refined. A novel, computationally efficient analytical Jacobian for NKM was developed to solve unsteady incompressible Navier-Stokes momentum equations on staggered curvilinear grids with immersed boundaries. The NKM was validated and verified against Taylor-Green vortex and pulsatile flow in a 90 degree bend and efficiently handles complex geometries such as an intracranial aneurysm with multiple overset grids, pulsatile inlet flow and immersed boundaries. The NKM method is shown to be more efficient than the semi-implicit Runge-Kutta methods and Jabobian-free Newton-Krylov methods. We believe NKM can be applied to many CFD techniques to decrease the computational cost. This work was supported partly by the NIH Grant R03EB014860, and the computational resources were partly provided by Center for Computational Research (CCR) at University at Buffalo.
Subspace methods for computational relighting
NASA Astrophysics Data System (ADS)
Nguyen, Ha Q.; Liu, Siying; Do, Minh N.
2013-02-01
We propose a vector space approach for relighting a Lambertian convex object with distant light source, whose crucial task is the decomposition of the reflectance function into albedos (or reflection coefficients) and lightings based on a set of images of the same object and its 3-D model. Making use of the fact that reflectance functions are well approximated by a low-dimensional linear subspace spanned by the first few spherical harmonics, this inverse problem can be formulated as a matrix factorization, in which the basis of the subspace is encoded in the spherical harmonic matrix S. A necessary and sufficient condition on S for unique factorization is derived with an introduction to a new notion of matrix rank called nonseparable full rank. An SVD-based algorithm for exact factorization in the noiseless case is introduced. In the presence of noise, the algorithm is slightly modified by incorporating the positivity of albedos into a convex optimization problem. Implementations of the proposed algorithms are done on a set of synthetic data.
An accelerated subspace iteration for eigenvector derivatives
NASA Technical Reports Server (NTRS)
Ting, Tienko
1991-01-01
An accelerated subspace iteration method for calculating eigenvector derivatives has been developed. Factors affecting the effectiveness and the reliability of the subspace iteration are identified, and effective strategies concerning these factors are presented. The method has been implemented, and the results of a demonstration problem are presented.
Preconditioned Iterative Solver
Energy Science and Technology Software Center (ESTSC)
2002-08-01
AztecOO contains a collection of preconditioned iterative methods for the solution of sparse linear systems of equations. In addition to providing many of the common algebraic preconditioners and basic iterative methods, AztecOO can be easily extended to interact with user-provided preconditioners and matrix operators.
Face recognition with L1-norm subspaces
NASA Astrophysics Data System (ADS)
Maritato, Federica; Liu, Ying; Colonnese, Stefania; Pados, Dimitris A.
2016-05-01
We consider the problem of representing individual faces by maximum L1-norm projection subspaces calculated from available face-image ensembles. In contrast to conventional L2-norm subspaces, L1-norm subspaces are seen to offer significant robustness to image variations, disturbances, and rank selection. Face recognition becomes then the problem of associating a new unknown face image to the "closest," in some sense, L1 subspace in the database. In this work, we also introduce the concept of adaptively allocating the available number of principal components to different face image classes, subject to a given total number/budget of principal components. Experimental studies included in this paper illustrate and support the theoretical developments.
Shadid, J. N.; Pawlowski, R. P.; Cyr, E. C.; Tuminaro, R. S.; Chacon, L.; Weber, P. D.
2016-02-10
Here, we discuss that the computational solution of the governing balance equations for mass, momentum, heat transfer and magnetic induction for resistive magnetohydrodynamics (MHD) systems can be extremely challenging. These difficulties arise from both the strong nonlinear, nonsymmetric coupling of fluid and electromagnetic phenomena, as well as the significant range of time- and length-scales that the interactions of these physical mechanisms produce. This paper explores the development of a scalable, fully-implicit stabilized unstructured finite element (FE) capability for 3D incompressible resistive MHD. The discussion considers the development of a stabilized FE formulation in context of the variational multiscale (VMS) method,more » and describes the scalable implicit time integration and direct-to-steady-state solution capability. The nonlinear solver strategy employs Newton–Krylov methods, which are preconditioned using fully-coupled algebraic multilevel preconditioners. These preconditioners are shown to enable a robust, scalable and efficient solution approach for the large-scale sparse linear systems generated by the Newton linearization. Verification results demonstrate the expected order-of-accuracy for the stabilized FE discretization. The approach is tested on a variety of prototype problems, that include MHD duct flows, an unstable hydromagnetic Kelvin–Helmholtz shear layer, and a 3D island coalescence problem used to model magnetic reconnection. Initial results that explore the scaling of the solution methods are also presented on up to 128K processors for problems with up to 1.8B unknowns on a CrayXK7.« less
A Hybrid, Parallel Krylov Solver for MODFLOW using Schwarz Domain Decomposition
NASA Astrophysics Data System (ADS)
Sutanudjaja, E.; Verkaik, J.; Hughes, J. D.
2015-12-01
In order to support decision makers in solving hydrological problems, detailed high-resolution models are often needed. These models typically consist of a large number of computational cells and have large memory requirements and long run times. An efficient technique for obtaining realistic run times and memory requirements is parallel computing, where the problem is divided over multiple processor cores. The new Parallel Krylov Solver (PKS) for MODFLOW-USG is presented. It combines both distributed memory parallelization by the Message Passing Interface (MPI) and shared memory parallelization by Open Multi-Processing (OpenMP). PKS includes conjugate gradient and biconjugate gradient stabilized linear accelerators that are both preconditioned by an overlapping additive Schwarz preconditioner in a way that: a) subdomains are partitioned using the METIS library; b) each subdomain uses local memory only and communicates with other subdomains by MPI within the linear accelerator; c) is fully integrated in the MODFLOW-USG code. PKS is based on the unstructured PCGU-solver, and supports OpenMP. Depending on the available hardware, PKS can run exclusively with MPI, exclusively with OpenMP, or with a hybrid MPI/OpenMP approach. Benchmarks were performed on the Cartesius Dutch supercomputer (https://userinfo.surfsara.nl/systems/cartesius) using up to 144 cores, for a synthetic test (~112 million cells) and the Indonesia groundwater model (~4 million 1km cells). The latter, which includes all islands in the Indonesian archipelago, was built using publically available global datasets, and is an ideal test bed for evaluating the applicability of PKS parallelization techniques to a global groundwater model consisting of multiple continents and islands. Results show that run time reductions can be greatest with the hybrid parallelization approach for the problems tested.
Bakhos, Tania; Saibaba, Arvind K.; Kitanidis, Peter K.
2015-10-15
We consider the problem of estimating parameters in large-scale weakly nonlinear inverse problems for which the underlying governing equations is a linear, time-dependent, parabolic partial differential equation. A major challenge in solving these inverse problems using Newton-type methods is the computational cost associated with solving the forward problem and with repeated construction of the Jacobian, which represents the sensitivity of the measurements to the unknown parameters. Forming the Jacobian can be prohibitively expensive because it requires repeated solutions of the forward and adjoint time-dependent parabolic partial differential equations corresponding to multiple sources and receivers. We propose an efficient method based on a Laplace transform-based exponential time integrator combined with a flexible Krylov subspace approach to solve the resulting shifted systems of equations efficiently. Our proposed solver speeds up the computation of the forward and adjoint problems, thus yielding significant speedup in total inversion time. We consider an application from Transient Hydraulic Tomography (THT), which is an imaging technique to estimate hydraulic parameters related to the subsurface from pressure measurements obtained by a series of pumping tests. The algorithms discussed are applied to a synthetic example taken from THT to demonstrate the resulting computational gains of this proposed method.
Zou, Ling; Zhao, Haihua; Zhang, Hongbin
2016-08-24
This study presents a numerical investigation on using the Jacobian-free Newton–Krylov (JFNK) method to solve the two-phase flow four-equation drift flux model with realistic constitutive correlations (‘closure models’). The drift flux model is based on Isshi and his collaborators’ work. Additional constitutive correlations for vertical channel flow, such as two-phase flow pressure drop, flow regime map, wall boiling and interfacial heat transfer models, were taken from the RELAP5-3D Code Manual and included to complete the model. The staggered grid finite volume method and fully implicit backward Euler method was used for the spatial discretization and time integration schemes, respectively. Themore » Jacobian-free Newton–Krylov method shows no difficulty in solving the two-phase flow drift flux model with a discrete flow regime map. In addition to the Jacobian-free approach, the preconditioning matrix is obtained by using the default finite differencing method provided in the PETSc package, and consequently the labor-intensive implementation of complex analytical Jacobian matrix is avoided. Extensive and successful numerical verification and validation have been performed to prove the correct implementation of the models and methods. Code-to-code comparison with RELAP5-3D has further demonstrated the successful implementation of the drift flux model.« less
Numerical solution of large nonsymmetric eigenvalue problems
NASA Technical Reports Server (NTRS)
Saad, Youcef
1988-01-01
Several methods are discribed for combinations of Krylov subspace techniques, deflation procedures and preconditionings, for computing a small number of eigenvalues and eigenvectors or Schur vectors of large sparse matrices. The most effective techniques for solving realistic problems from applications are those methods based on some form of preconditioning and one of several Krylov subspace techniques, such as Arnoldi's method or Lanczos procedure. Two forms of preconditioning are considered: shift-and-invert and polynomial acceleration. The latter presents some advantages for parallel/vector processing but may be ineffective if eigenvalues inside the spectrum are sought. Some algorithmic details are provided that improve the reliability and effectiveness of these techniques.
Signal subspace integration for improved seizure localization
Stamoulis, Catherine; Fernández, Iván Sánchez; Chang, Bernard S.; Loddenkemper, Tobias
2012-01-01
A subspace signal processing approach is proposed for improved scalp EEG-based localization of broad-focus epileptic seizures, and estimation of the directions of source arrivals (DOA). Ictal scalp EEGs from adult and pediatric patients with broad-focus seizures were first decomposed into dominant signal modes, and signal and noise subspaces at each modal frequency, to improve the signal-to-noise ratio while preserving the original data correlation structure. Transformed (focused) modal signals were then resynthesized into wideband signals from which the number of sources and DOA were estimated. These were compared to denoised signals via principal components analysis (PCA). Coherent subspace processing performed better than PCA, significantly improved the localization of ictal EEGs and the estimation of distinct sources and corresponding DOAs. PMID:23366067
Signal subspace integration for improved seizure localization.
Stamoulis, Catherine; Fernández, Iván Sánchez; Chang, Bernard S; Loddenkemper, Tobias
2012-01-01
A subspace signal processing approach is proposed for improved scalp EEG-based localization of broad-focus epileptic seizures, and estimation of the directions of source arrivals (DOA). Ictal scalp EEGs from adult and pediatric patients with broad-focus seizures were first decomposed into dominant signal modes, and signal and noise subspaces at each modal frequency, to improve the signal-to-noise ratio while preserving the original data correlation structure. Transformed (focused) modal signals were then resynthesized into wideband signals from which the number of sources and DOA were estimated. These were compared to denoised signals via principal components analysis (PCA). Coherent subspace processing performed better than PCA, significantly improved the localization of ictal EEGs and the estimation of distinct sources and corresponding DOAs. PMID:23366067
Sparse subspace clustering: algorithm, theory, and applications.
Elhamifar, Ehsan; Vidal, René
2013-11-01
Many real-world problems deal with collections of high-dimensional data, such as images, videos, text, and web documents, DNA microarray data, and more. Often, such high-dimensional data lie close to low-dimensional structures corresponding to several classes or categories to which the data belong. In this paper, we propose and study an algorithm, called sparse subspace clustering, to cluster data points that lie in a union of low-dimensional subspaces. The key idea is that, among the infinitely many possible representations of a data point in terms of other points, a sparse representation corresponds to selecting a few points from the same subspace. This motivates solving a sparse optimization program whose solution is used in a spectral clustering framework to infer the clustering of the data into subspaces. Since solving the sparse optimization program is in general NP-hard, we consider a convex relaxation and show that, under appropriate conditions on the arrangement of the subspaces and the distribution of the data, the proposed minimization program succeeds in recovering the desired sparse representations. The proposed algorithm is efficient and can handle data points near the intersections of subspaces. Another key advantage of the proposed algorithm with respect to the state of the art is that it can deal directly with data nuisances, such as noise, sparse outlying entries, and missing entries, by incorporating the model of the data into the sparse optimization program. We demonstrate the effectiveness of the proposed algorithm through experiments on synthetic data as well as the two real-world problems of motion segmentation and face clustering. PMID:24051734
Subspace Identification with Multiple Data Sets
NASA Technical Reports Server (NTRS)
Duchesne, Laurent; Feron, Eric; Paduano, James D.; Brenner, Marty
1995-01-01
Most existing subspace identification algorithms assume that a single input to output data set is available. Motivated by a real life problem on the F18-SRA experimental aircraft, we show how these algorithms are readily adapted to handle multiple data sets. We show by means of an example the relevance of such an improvement.
Applications of Subspace Seismicity Detection in Antarctica
NASA Astrophysics Data System (ADS)
Myers, E. K.; Aster, R. C.; Benz, H.; McMahon, N. D.; McNamara, D. E.; Lough, A. C.; Wiens, D. A.; Wilson, T. J.
2014-12-01
Subspace detection can improve event recognition by enhancing the completeness of earthquake catalogs and by improving the characterization and interpretation of seismic events, particularly in regions of clustered seismicity. Recent deployments of dense networks of seismometers enable subspace detection methods to be more broadly applied to intraplate Antarctica, where historically very limited and sporadic network coverage has inhibited understanding of dynamic glacial, volcanic, and tectonic processes. In particular, recent broad seismographic networks such as POLENET/A-Net and AGAP provide significant new opportunities for characterizing and understanding the low seismicity rates of this continent. Our methodology incorporates three-component correlation to detect events in a statistical and adaptive framework. Detection thresholds are statistically assessed using phase-randomized template correlation levels. As new events are detected and the set of subspace basis vectors is updated, the algorithm can also be directed to scan back in a search for weaker prior events that have significant correlations with the updated basis vectors. This method has the resolving power to identify previously undetected areas of seismic activity under very low signal-to-noise conditions, and thus holds promise for revealing new seismogenic phenomena within and around Antarctica. In this study we investigate two intriguing seismogenic regions and demonstrate the methodology, reporting on a subspace detection-based study of recently identified clusters of deep long-period magmatic earthquakes in Marie Byrd Land, and on shallow icequakes that are dynamically triggered by teleseismic surface waves.
Real Space DFT by Locally Optimal Block Preconditioned Conjugate Gradient Method
NASA Astrophysics Data System (ADS)
Michaud, Vincent; Guo, Hong
2012-02-01
Real space approaches solve the Kohn-Sham (KS) DFT problem as a system of partial differential equations (PDE) in real space numerical grids. In such techniques, the Hamiltonian matrix is typically much larger but sparser than the matrix arising in state-of-the-art DFT codes which are often based on directly minimizing the total energy functional. Evidence of good performance of real space methods - by Chebyshev filtered subspace iteration (CFSI) - was reported by Zhou, Saad, Tiago and Chelikowsky [1]. We found that the performance of the locally optimal block preconditioned conjugate gradient method (LOGPCG) introduced by Knyazev [2], when used in conjunction with CFSI, generally exceeds that of CFSI for solving the KS equations. We will present our implementation of the LOGPCG based real space electronic structure calculator. [4pt] [1] Y. Zhou, Y. Saad, M. L. Tiago, and J. R. Chelikowsky, ``Self-consistent-field calculations using Chebyshev-filtered subspace iteration,'' J. Comput. Phys., vol. 219,pp. 172-184, November 2006. [0pt] [2] A. V. Knyazev, ``Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method,'' SIAM J. Sci. Comput, vol. 23, pp. 517-541, 2001.
Exploiting Unsupervised and Supervised Constraints for Subspace Clustering.
Hu, Han; Feng, Jianjiang; Zhou, Jie
2015-08-01
Data in many image and video analysis tasks can be viewed as points drawn from multiple low-dimensional subspaces with each subspace corresponding to one category or class. One basic task for processing such kind of data is to separate the points according to the underlying subspace, referred to as subspace clustering. Extensive studies have been made on this subject, and nearly all of them use unconstrained subspace models, meaning the points can be drawn from everywhere of a subspace, to represent the data. In this paper, we attempt to do subspace clustering based on a constrained subspace assumption that the data is further restricted in the corresponding subspaces, e.g., belonging to a submanifold or satisfying the spatial regularity constraint. This assumption usually describes the real data better, such as differently moving objects in a video scene and face images of different subjects under varying illumination. A unified integer linear programming optimization framework is used to approach subspace clustering, which can be efficiently solved by a branch-and-bound (BB) method. We also show that various kinds of supervised information, such as subspace number, outlier ratio, pairwise constraints, size prior and etc., can be conveniently incorporated into the proposed framework. Experiments on real data show that the proposed method outperforms the state-of-the-art algorithms significantly in clustering accuracy. The effectiveness of the proposed method in exploiting supervised information is also demonstrated. PMID:26352994
Vecharynski, Eugene; Yang, Chao; Pask, John E.
2015-06-01
We present an iterative algorithm for computing an invariant subspace associated with the algebraically smallest eigenvalues of a large sparse or structured Hermitian matrix A. We are interested in the case in which the dimension of the invariant subspace is large (e.g., over several hundreds or thousands) even though it may still be small relative to the dimension of A. These problems arise from, for example, density functional theory (DFT) based electronic structure calculations for complex materials. The key feature of our algorithm is that it performs fewer Rayleigh–Ritz calculations compared to existing algorithms such as the locally optimal block preconditioned conjugate gradient or the Davidson algorithm. It is a block algorithm, and hence can take advantage of efficient BLAS3 operations and be implemented with multiple levels of concurrency. We discuss a number of practical issues that must be addressed in order to implement the algorithm efficiently on a high performance computer.
General purpose nonlinear system solver based on Newton-Krylov method.
Energy Science and Technology Software Center (ESTSC)
2013-12-01
KINSOL is part of a software family called SUNDIALS: SUite of Nonlinear and Differential/Algebraic equation Solvers [1]. KINSOL is a general-purpose nonlinear system solver based on Newton-Krylov and fixed-point solver technologies [2].
Discriminative Semantic Subspace Analysis for Relevance Feedback.
Zhang, Lining; Shum, Hubert P H; Shao, Ling
2016-03-01
Content-based image retrieval (CBIR) has attracted much attention during the past decades for its potential practical applications to image database management. A variety of relevance feedback (RF) schemes have been designed to bridge the gap between low-level visual features and high-level semantic concepts for an image retrieval task. In the process of RF, it would be impractical or too expensive to provide explicit class label information for each image. Instead, similar or dissimilar pairwise constraints between two images can be acquired more easily. However, most of the conventional RF approaches can only deal with training images with explicit class label information. In this paper, we propose a novel discriminative semantic subspace analysis (DSSA) method, which can directly learn a semantic subspace from similar and dissimilar pairwise constraints without using any explicit class label information. In particular, DSSA can effectively integrate the local geometry of labeled similar images, the discriminative information between labeled similar and dissimilar images, and the local geometry of labeled and unlabeled images together to learn a reliable subspace. Compared with the popular distance metric analysis approaches, our method can also learn a distance metric but perform more effectively when dealing with high-dimensional images. Extensive experiments on both the synthetic data sets and a real-world image database demonstrate the effectiveness of the proposed scheme in improving the performance of the CBIR. PMID:26780793
HyeongKae Park; R. Nourgaliev; Richard C. Martineau; Dana A. Knoll
2008-09-01
Multidimensional, higher-order (2nd and higher) numerical methods have come to the forefront in recent years due to significant advances of computer technology and numerical algorithms, and have shown great potential as viable design tools for realistic applications. To achieve this goal, implicit high-order accurate coupling of the multiphysics simulations is a critical component. One of the issues that arise from multiphysics simulation is the necessity to resolve multiple time scales. For example, the dynamical time scales of neutron kinetics, fluid dynamics and heat conduction significantly differ (typically >1010 magnitude), with the dominant (fastest) physical mode also changing during the course of transient [Pope and Mousseau, 2007]. This leads to the severe time step restriction for stability in traditional multiphysics (i.e. operator split, semi-implicit discretization) simulations. The lower order methods suffer from an undesirable numerical dissipation. Thus implicit, higher order accurate scheme is necessary to perform seamlessly-coupled multiphysics simulations that can be used to analyze the “what-if” regulatory accident scenarios, or to design and optimize engineering systems.
Iterative methods for large scale nonlinear and linear systems. Final report, 1994--1996
Walker, H.F.
1997-09-01
The major goal of this research has been to develop improved numerical methods for the solution of large-scale systems of linear and nonlinear equations, such as occur almost ubiquitously in the computational modeling of physical phenomena. The numerical methods of central interest have been Krylov subspace methods for linear systems, which have enjoyed great success in many large-scale applications, and newton-Krylov methods for nonlinear problems, which use Krylov subspace methods to solve approximately the linear systems that characterize Newton steps. Krylov subspace methods have undergone a remarkable development over the last decade or so and are now very widely used for the iterative solution of large-scale linear systems, particularly those that arise in the discretization of partial differential equations (PDEs) that occur in computational modeling. Newton-Krylov methods have enjoyed parallel success and are currently used in many nonlinear applications of great scientific and industrial importance. In addition to their effectiveness on important problems, Newton-Krylov methods also offer a nonlinear framework within which to transfer to the nonlinear setting any advances in Krylov subspace methods or preconditioning techniques, or new algorithms that exploit advanced machine architectures. This research has resulted in a number of improved Krylov and Newton-Krylov algorithms together with applications of these to important linear and nonlinear problems.
Indoor Subspacing to Implement Indoorgml for Indoor Navigation
NASA Astrophysics Data System (ADS)
Jung, H.; Lee, J.
2015-10-01
According to an increasing demand for indoor navigation, there are great attempts to develop applicable indoor network. Representation for a room as a node is not sufficient to apply complex and large buildings. As OGC established IndoorGML, subspacing to partition the space for constructing logical network is introduced. Concerning subspacing for indoor network, transition space like halls or corridors also have to be considered. This study presents the subspacing process for creating an indoor network in shopping mall. Furthermore, categorization of transition space is performed and subspacing of this space is considered. Hall and squares in mall is especially defined for subspacing. Finally, implementation of subspacing process for indoor network is presented.
Biomarkers for ischemic preconditioning: finding the responders
Koch, Sebastian; Della-Morte, David; Dave, Kunjan R; Sacco, Ralph L; Perez-Pinzon, Miguel A
2014-01-01
Ischemic preconditioning is emerging as an innovative and novel cytoprotective strategy to counter ischemic vascular disease. At the root of the preconditioning response is the upregulation of endogenous defense systems to achieve ischemic tolerance. Identifying suitable biomarkers to show that a preconditioning response has been induced remains a translational research priority. Preconditioning leads to a widespread genomic and proteonomic response with important effects on hemostatic, endothelial, and inflammatory systems. The present article summarizes the relevant preclinical studies defining the mechanisms of preconditioning, reviews how the human preconditioning response has been investigated, and which of these bioresponses could serve as a suitable biomarker. Human preconditioning studies have investigated the effects of preconditioning on coagulation, endothelial factors, and inflammatory mediators as well as on genetic expression and tissue blood flow imaging. A biomarker for preconditioning would significantly contribute to define the optimal preconditioning stimulus and the extent to which such a response can be elicited in humans and greatly aid in dose selection in the design of phase II trials. Given the manifold biologic effects of preconditioning a panel of multiple serum biomarkers or genomic assessments of upstream regulators may most accurately reflect the full spectrum of a preconditioning response. PMID:24643082
Orderings for conjugate gradient preconditionings
NASA Technical Reports Server (NTRS)
Ortega, James M.
1991-01-01
The effect of orderings on the rate of convergence of the conjugate gradient method with SSOR or incomplete Cholesky preconditioning is examined. Some results also are presented that help to explain why red/black ordering gives an inferior rate of convergence.
Hyperbaric oxygen pretreatment and preconditioning.
Camporesi, Enrico M; Bosco, Gerardo
2014-01-01
Exposure to hyperbaric oxygen (HBO2) before a crucial event, with the plan to create a preventing therapeutic situation, has been defined "preconditioning" and is emerging as a useful adjunct both in diving medicine as well before ischemic or inflammatory events. Oxygen pre-breathing before diving has been extensively documented in recreational, technical, commercial and military diving for tissue denitrogenation, resulting in reduced post-diving bubble loads, reduced decompression requirements and more rapid return to normal platelet function after a decompression. Preoxygenation at high atmospheric pressure has also been used in patients before exposure to clinical situations with beneficial effects, but the mechanisms of action have not yet been ascertained. During the reperfusion of ischemic tissue, oxygenated blood increases numbers and activities of oxidants generated in tissues. Previous reports showed that HBO2 preconditioning caused the activation of antioxidative enzymes and related genes in the central nervous system, including catalase (CAT), superoxide dismutase and heme oxygenase-1. Despite the increasing number of basic science publications on this issue, studies describing HBO2 preconditioning in the clinical practice remain scarce. To date, only a few studies have investigated the preconditioning effects of HBO2 in relation to the human brain and myocardium with robust and promising results. PMID:24984322
The variational subspace valence bond method
Fletcher, Graham D.
2015-04-07
The variational subspace valence bond (VSVB) method based on overlapping orbitals is introduced. VSVB provides variational support against collapse for the optimization of overlapping linear combinations of atomic orbitals (OLCAOs) using modified orbital expansions, without recourse to orthogonalization. OLCAO have the advantage of being naturally localized, chemically intuitive (to individually model bonds and lone pairs, for example), and transferrable between different molecular systems. Such features are exploited to avoid key computational bottlenecks. Since the OLCAO can be doubly occupied, VSVB can access very large problems, and calculations on systems with several hundred atoms are presented.
Signal Subspace Processing Of Experimental Radio Data
NASA Astrophysics Data System (ADS)
Martin, Gordon E.
1988-02-01
The research related to this paper was concerned with the application of EigenVector EigenValue ( EVEV ) signal processing techniques to experimental data. The signal subspace methods of Schmidt (called MUSIC), Johnson, and Pisarenko were considered and compared with results of conventional beamformers. Almost all oral and written papers regarding these EVEV processors involve theoretical studies, possibly using simulated data and incoherent noise, but not experimental data. Contrary to that trend, we have reported behavior of EVEV processors using experimental data in this and other papers. The data used here are predominantly due to an HF radio experiment, but the distribution of eigenvalues is also reported for acoustic data. The paper emphasizes two general subtopics of signal subspace processing. First, the eigenvalues of sampled covariance matrices are examined and related to those of incoherent noise. These results include actual data, all of which we found were not Gaussian incoherent noise. A new test related to the ratio of eigenvalues is developed. The MDL and AIC criteria give misleading results with actual noise. Second, directional responses of EVEV and conventional processors are compared using HF radio data that has high signal-to-noise ratio in the non-Gaussian noise. MUSIC is found to have very favorable directional characteristics.
On the dimension of subspaces with bounded Schmidt rank
Cubitt, Toby; Montanaro, Ashley; Winter, Andreas
2008-02-15
We consider the question of how large a subspace of a given bipartite quantum system can be when the subspace contains only highly entangled states. This is motivated in part by results of Hayden et al. [e-print arXiv:quant-ph/0407049; Commun. Math. Phys., 265, 95 (2006)], which show that in large dxd-dimensional systems there exist random subspaces of dimension almost d{sup 2}, all of whose states have entropy of entanglement at least log d-O(1). It is also a generalization of results on the dimension of completely entangled subspaces, which have connections with the construction of unextendible product bases. Here we take as entanglement measure the Schmidt rank, and determine, for every pair of local dimensions d{sub A} and d{sub B}, and every r, the largest dimension of a subspace consisting only of entangled states of Schmidt rank r or larger. This exact answer is a significant improvement on the best bounds that can be obtained using the random subspace techniques in Hayden et al. We also determine the converse: the largest dimension of a subspace with an upper bound on the Schmidt rank. Finally, we discuss the question of subspaces containing only states with Schmidt equal to r.
Classes of Invariant Subspaces for Some Operator Algebras
NASA Astrophysics Data System (ADS)
Hamhalter, Jan; Turilova, Ekaterina
2014-10-01
New results showing connections between structural properties of von Neumann algebras and order theoretic properties of structures of invariant subspaces given by them are proved. We show that for any properly infinite von Neumann algebra M there is an affiliated subspace such that all important subspace classes living on are different. Moreover, we show that can be chosen such that the set of σ-additive measures on subspace classes of are empty. We generalize measure theoretic criterion on completeness of inner product spaces to affiliated subspaces corresponding to Type I factor with finite dimensional commutant. We summarize hitherto known results in this area, discuss their importance for mathematical foundations of quantum theory, and outline perspectives of further research.
Subspace segmentation by dense block and sparse representation.
Tang, Kewei; Dunson, David B; Su, Zhixun; Liu, Risheng; Zhang, Jie; Dong, Jiangxin
2016-03-01
Subspace segmentation is a fundamental topic in computer vision and machine learning. However, the success of many popular methods is about independent subspace segmentation instead of the more flexible and realistic disjoint subspace segmentation. Focusing on the disjoint subspaces, we provide theoretical and empirical evidence of inferior performance for popular algorithms such as LRR. To solve these problems, we propose a novel dense block and sparse representation (DBSR) for subspace segmentation and provide related theoretical results. DBSR minimizes a combination of the 1,1-norm and maximum singular value of the representation matrix, leading to a combination of dense block and sparsity. We provide experimental results for synthetic and benchmark data showing that our method can outperform the state-of-the-art. PMID:26720247
Preconditioning Operators on Unstructured Grids
NASA Technical Reports Server (NTRS)
Nepomnyaschikh, S. V.
1996-01-01
We consider systems of mesh equations that approximate elliptic boundary value problems on arbitrary (unstructured) quasi-uniform triangulations and propose a method for constructing optimal preconditioning operators. The method is based upon two approaches: (1) the fictitious space method, i.e., the reduction of the original problem to a problem in an auxiliary (fictitious) space, and (2) the multilevel decomposition method, i.e., the construction of preconditioners by decomposing functions on hierarchical meshes. The convergence rate of the corresponding iterative process with the preconditioner obtained is independent of the mesh step. The preconditioner has an optimal computational cost: the number of arithmetic operations required for its implementation is proportional to the number of unknowns in the problem. The construction of the preconditioning operators for three dimensional problems can be done in the same way.
Cerebral Ischemic Preconditioning: the Road So Far….
Thushara Vijayakumar, N; Sangwan, Amit; Sharma, Bhargy; Majid, Arshad; Rajanikant, G K
2016-05-01
Cerebral preconditioning constitutes the brain's adaptation to lethal ischemia when first exposed to mild doses of a subtoxic stressor. The phenomenon of preconditioning has been largely studied in the heart, and data from in vivo and in vitro models from past 2-3 decades have provided sufficient evidence that similar machinery exists in the brain as well. Since preconditioning results in a transient protective phenotype labeled as ischemic tolerance, it can open many doors in the medical warfare against stroke, a debilitating cerebrovascular disorder that kills or cripples thousands of people worldwide every year. Preconditioning can be induced by a variety of stimuli from hypoxia to pharmacological anesthetics, and each, in turn, induces tolerance by activating a multitude of proteins, enzymes, receptors, transcription factors, and other biomolecules eventually leading to genomic reprogramming. The intracellular signaling pathways and molecular cascades behind preconditioning are extensively being investigated, and several first-rate papers have come out in the last few years centered on the topic of cerebral ischemic tolerance. However, translating the experimental knowledge into the clinical scaffold still evades practicality and faces several challenges. Of the various preconditioning strategies, remote ischemic preconditioning and pharmacological preconditioning appears to be more clinically relevant for the management of ischemic stroke. In this review, we discuss current developments in the field of cerebral preconditioning and then examine the potential of various preconditioning agents to confer neuroprotection in the brain. PMID:26081149
[Pharmacological preconditioning in carotid endarterectomy].
Kuznetsov, M R; Karalkin, A V; Fedin, A I; Virganskii, A O; Kunitsyn, N V; Kholopova, E A; Yumin, S M
2015-01-01
The study was aimed at examining efficacy of preoperative preparation (pharmacological preconditioning) for carotid endarterectomy in patients with chronic cerebrovascular insufficiency. For this purpose, we analysed the outcomes of surgical treatment in a total of 80 patients presenting with haemodynamically significant unilateral and bilateral lesions of carotid arteries. Of these, 40 patients were operated on immediately and a further 40 patients underwent surgery after pharmacological preconditioning with Actovegin taken at a daily dose of 1,200 mg for 1.5 months. It was demonstrated that preoperative preparation prior to surgery increases cerebral perfusion which is determined by means of single-photon emission computed tomography, thus substantially improving the outcomes of surgical treatment. Statistically significant differences in cognitive function of these groups of patients were revealed 7 days and 6 months after the operation. Improvement of cognitive functions was associated with fewer symptom-free postoperative cerebral ischaemic foci in various regions of the brain. A conclusion was made on a positive role of pharmacological preconditioning with Actovegin in surgical management of cerebrovascular insufficiency, first of all in relation to more complete restoration of cognitive functions. PMID:26355920
Preconditioning for traumatic brain injury
Yokobori, Shoji; Mazzeo, Anna T; Hosein, Khadil; Gajavelli, Shyam; Dietrich, W. Dalton; Bullock, M. Ross
2016-01-01
Traumatic brain injury (TBI) treatment is now focused on the prevention of primary injury and reduction of secondary injury. However, no single effective treatment is available as yet for the mitigation of traumatic brain damage in humans. Both chemical and environmental stresses applied before injury, have been shown to induce consequent protection against post-TBI neuronal death. This concept termed “preconditioning” is achieved by exposure to different pre-injury stressors, to achieve the induction of “tolerance” to the effect of the TBI. However, the precise mechanisms underlying this “tolerance” phenomenon are not fully understood in TBI, and therefore even less information is available about possible indications in clinical TBI patients. In this review we will summarize TBI pathophysiology, and discuss existing animal studies demonstrating the efficacy of preconditioning in diffuse and focal type of TBI. We will also review other non-TBI preconditionng studies, including ischemic, environmental, and chemical preconditioning, which maybe relevant to TBI. To date, no clinical studies exist in this field, and we speculate on possible futureclinical situation, in which pre-TBI preconditioning could be considered. PMID:24323189
NASA Astrophysics Data System (ADS)
Borazjani, Iman; Asgharzadeh, Hafez
2015-11-01
Flow simulations involving complex geometries and moving boundaries suffer from time-step size restriction and low convergence rates with explicit and semi-implicit schemes. Implicit schemes can be used to overcome these restrictions. However, implementing implicit solver for nonlinear equations including Navier-Stokes is not straightforward. Newton-Krylov subspace methods (NKMs) are one of the most advanced iterative methods to solve non-linear equations such as implicit descritization of the Navier-Stokes equation. The efficiency of NKMs massively depends on the Jacobian formation method, e.g., automatic differentiation is very expensive, and matrix-free methods slow down as the mesh is refined. Analytical Jacobian is inexpensive method, but derivation of analytical Jacobian for Navier-Stokes equation on staggered grid is challenging. The NKM with a novel analytical Jacobian was developed and validated against Taylor-Green vortex and pulsatile flow in a 90 degree bend. The developed method successfully handled the complex geometries such as an intracranial aneurysm with multiple overset grids, and immersed boundaries. It is shown that the NKM with an analytical Jacobian is 3 to 25 times faster than the fixed-point implicit Runge-Kutta method, and more than 100 times faster than automatic differentiation depending on the grid (size) and the flow problem. The developed methods are fully parallelized with parallel efficiency of 80-90% on the problems tested.
NASA Astrophysics Data System (ADS)
De Maio, Antonio; Orlando, Danilo
2016-04-01
This paper deals with adaptive radar detection of a subspace signal competing with two sources of interference. The former is Gaussian with unknown covariance matrix and accounts for the joint presence of clutter plus thermal noise. The latter is structured as a subspace signal and models coherent pulsed jammers impinging on the radar antenna. The problem is solved via the Principle of Invariance which is based on the identification of a suitable group of transformations leaving the considered hypothesis testing problem invariant. A maximal invariant statistic, which completely characterizes the class of invariant decision rules and significantly compresses the original data domain, as well as its statistical characterization are determined. Thus, the existence of the optimum invariant detector is addressed together with the design of practically implementable invariant decision rules. At the analysis stage, the performance of some receivers belonging to the new invariant class is established through the use of analytic expressions.
Faces from sketches: a subspace synthesis approach
NASA Astrophysics Data System (ADS)
Li, Yung-hui; Savvides, Marios
2006-04-01
In real life scenario, we may be interested in face recognition for identification purpose when we only got sketch of the face images, for example, when police tries to identify criminals based on sketches of suspect, which is drawn by artists according to description of witnesses, what they have in hand is a sketch of suspects, and many real face image acquired from video surveillance. So far the state-of-the-art approach toward this problem tries to transform all real face images into sketches and perform recognition on sketch domain. In our approach we propose the opposite which is a better approach; we propose to generate a realistic face image from the composite sketch using a Hybrid subspace method and then build an illumination tolerant correlation filter which can recognize the person under different illumination variations. We show experimental results on our approach on the CMU PIE (Pose Illumination and Expression) database on the effectiveness of our novel approach.
Coherent signal-subspace transformation beam former
NASA Astrophysics Data System (ADS)
Yang, J.-F.; Kaveh, M.
1990-08-01
A family of coherent signal-subspace transformation (CST) preprocessors for improving the performance of beam formers is presented. The proposed beam former includes a CST preprocessor followed by a frequency-independent mulling procedure. If the exact CST preprocessor is used, it is shown that the steering and nulling responses of the CST beam former become frequency independent. This CST beam former is also interpreted as a wideband minimum-variance distortionless response (MVDR) beam former for minimizing the total interference and noise powers. Several classes of the CST matrix are proposed and discussed. Unlike the traditional linearly constrained beam formers, the CST beam former effectively nulls the narrowband and wideband correlated interfences(s). Simulation results show that even low-order approximate CST preprocessors substantially improve the nulling and the steering bandwidth of general arrays.
Robust video hashing via multilinear subspace projections.
Li, Mu; Monga, Vishal
2012-10-01
The goal of video hashing is to design hash functions that summarize videos by short fingerprints or hashes. While traditional applications of video hashing lie in database searches and content authentication, the emergence of websites such as YouTube and DailyMotion poses a challenging problem of anti-piracy video search. That is, hashes or fingerprints of an original video (provided to YouTube by the content owner) must be matched against those uploaded to YouTube by users to identify instances of "illegal" or undesirable uploads. Because the uploaded videos invariably differ from the original in their digital representation (owing to incidental or malicious distortions), robust video hashes are desired. We model videos as order-3 tensors and use multilinear subspace projections, such as a reduced rank parallel factor analysis (PARAFAC) to construct video hashes. We observe that, unlike most standard descriptors of video content, tensor-based subspace projections can offer excellent robustness while effectively capturing the spatio-temporal essence of the video for discriminability. We introduce randomization in the hash function by dividing the video into (secret key based) pseudo-randomly selected overlapping sub-cubes to prevent against intentional guessing and forgery. Detection theoretic analysis of the proposed hash-based video identification is presented, where we derive analytical approximations for error probabilities. Remarkably, these theoretic error estimates closely mimic empirically observed error probability for our hash algorithm. Furthermore, experimental receiver operating characteristic (ROC) curves reveal that the proposed tensor-based video hash exhibits enhanced robustness against both spatial and temporal video distortions over state-of-the-art video hashing techniques. PMID:22752130
Preconditioned iterations to calculate extreme eigenvalues
Brand, C.W.; Petrova, S.
1994-12-31
Common iterative algorithms to calculate a few extreme eigenvalues of a large, sparse matrix are Lanczos methods or power iterations. They converge at a rate proportional to the separation of the extreme eigenvalues from the rest of the spectrum. Appropriate preconditioning improves the separation of the eigenvalues. Davidson`s method and its generalizations exploit this fact. The authors examine a preconditioned iteration that resembles a truncated version of Davidson`s method with a different preconditioning strategy.
Scalable parallel Newton-Krylov solvers for discontinuous Galerkin discretizations
Persson, P.-O.
2008-12-31
We present techniques for implicit solution of discontinuous Galerkin discretizations of the Navier-Stokes equations on parallel computers. While a block-Jacobi method is simple and straight-forward to parallelize, its convergence properties are poor except for simple problems. Therefore, we consider Newton-GMRES methods preconditioned with block-incomplete LU factorizations, with optimized element orderings based on a minimum discarded fill (MDF) approach. We discuss the difficulties with the parallelization of these methods, but also show that with a simple domain decomposition approach, most of the advantages of the block-ILU over the block-Jacobi preconditioner are still retained. The convergence is further improved by incorporating the matrix connectivities into the mesh partitioning process, which aims at minimizing the errors introduced from separating the partitions. We demonstrate the performance of the schemes for realistic two- and three-dimensional flow problems.
An alternative subspace approach to EEG dipole source localization
NASA Astrophysics Data System (ADS)
Xu, Xiao-Liang; Xu, Bobby; He, Bin
2004-01-01
In the present study, we investigate a new approach to electroencephalography (EEG) three-dimensional (3D) dipole source localization by using a non-recursive subspace algorithm called FINES. In estimating source dipole locations, the present approach employs projections onto a subspace spanned by a small set of particular vectors (FINES vector set) in the estimated noise-only subspace instead of the entire estimated noise-only subspace in the case of classic MUSIC. The subspace spanned by this vector set is, in the sense of principal angle, closest to the subspace spanned by the array manifold associated with a particular brain region. By incorporating knowledge of the array manifold in identifying FINES vector sets in the estimated noise-only subspace for different brain regions, the present approach is able to estimate sources with enhanced accuracy and spatial resolution, thus enhancing the capability of resolving closely spaced sources and reducing estimation errors. The present computer simulations show, in EEG 3D dipole source localization, that compared to classic MUSIC, FINES has (1) better resolvability of two closely spaced dipolar sources and (2) better estimation accuracy of source locations. In comparison with RAP-MUSIC, FINES' performance is also better for the cases studied when the noise level is high and/or correlations among dipole sources exist.
An alternative subspace approach to EEG dipole source localization.
Xu, Xiao-Liang; Xu, Bobby; He, Bin
2004-01-21
In the present study, we investigate a new approach to electroencephalography (EEG) three-dimensional (3D) dipole source localization by using a non-recursive subspace algorithm called FINES. In estimating source dipole locations, the present approach employs projections onto a subspace spanned by a small set of particular vectors (FINES vector set) in the estimated noise-only subspace instead of the entire estimated noise-only subspace in the case of classic MUSIC. The subspace spanned by this vector set is, in the sense of principal angle, closest to the subspace spanned by the array manifold associated with a particular brain region. By incorporating knowledge of the array manifold in identifying FINES vector sets in the estimated noise-only subspace for different brain regions, the present approach is able to estimate sources with enhanced accuracy and spatial resolution, thus enhancing the capability of resolving closely spaced sources and reducing estimation errors. The present computer simulations show, in EEG 3D dipole source localization, that compared to classic MUSIC, FINES has (1) better resolvability of two closely spaced dipolar sources and (2) better estimation accuracy of source locations. In comparison with RAP-MUSIC, FINES' performance is also better for the cases studied when the noise level is high and/or correlations among dipole sources exist. PMID:15083674
Learning Markov Random Walks for robust subspace clustering and estimation.
Liu, Risheng; Lin, Zhouchen; Su, Zhixun
2014-11-01
Markov Random Walks (MRW) has proven to be an effective way to understand spectral clustering and embedding. However, due to less global structural measure, conventional MRW (e.g., the Gaussian kernel MRW) cannot be applied to handle data points drawn from a mixture of subspaces. In this paper, we introduce a regularized MRW learning model, using a low-rank penalty to constrain the global subspace structure, for subspace clustering and estimation. In our framework, both the local pairwise similarity and the global subspace structure can be learnt from the transition probabilities of MRW. We prove that under some suitable conditions, our proposed local/global criteria can exactly capture the multiple subspace structure and learn a low-dimensional embedding for the data, in which giving the true segmentation of subspaces. To improve robustness in real situations, we also propose an extension of the MRW learning model based on integrating transition matrix learning and error correction in a unified framework. Experimental results on both synthetic data and real applications demonstrate that our proposed MRW learning model and its robust extension outperform the state-of-the-art subspace clustering methods. PMID:25005156
Latent subspace sparse representation-based unsupervised domain adaptation
NASA Astrophysics Data System (ADS)
Shuai, Liu; Sun, Hao; Zhao, Fumin; Zhou, Shilin
2015-12-01
In this paper, we introduce and study a novel unsupervised domain adaptation (DA) algorithm, called latent subspace sparse representation based domain adaptation, based on the fact that source and target data that lie in different but related low-dimension subspaces. The key idea is that each point in a union of subspaces can be constructed by a combination of other points in the dataset. In this method, we propose to project the source and target data onto a common latent generalized subspace which is a union of subspaces of source and target domains and learn the sparse representation in the latent generalized subspace. By employing the minimum reconstruction error and maximum mean discrepancy (MMD) constraints, the structure of source and target domain are preserved and the discrepancy is reduced between the source and target domains and thus reflected in the sparse representation. We then utilize the sparse representation to build a weighted graph which reflect the relationship of points from the different domains (source-source, source- target, and target-target) to predict the labels of the target domain. We also proposed an efficient optimization method for the algorithm. Our method does not need to combine with any classifiers and therefore does not need train the test procedures. Various experiments show that the proposed method perform better than the competitive state of art subspace-based domain adaptation.
Management of Preconditioned Calves and Impacts of Preconditioning.
Hilton, W Mark
2015-07-01
When studying the practice of preconditioning (PC) calves, many factors need to be examined to determine if cow-calf producers should make this investment. Factors such as average daily gain, feed efficiency, available labor, length of the PC period, genetics, and marketing options must be analyzed. The health sales price advantage is an additional benefit in producing and selling PC calves but not the sole determinant of PC's financially feasibility. Studies show that a substantial advantage of PC is the selling of additional pounds at a cost of gain well below the marginal return of producing those additional pounds. PMID:26139187
Preconditioning for multidimensional TOMBO imaging.
Horisaki, Ryoichi; Tanida, Jun
2011-06-01
In this Letter, we propose a preconditioning method to improve the convergence speed of iterative reconstruction algorithms in a compact, multidimensional, compound-eye imaging system called the thin observation module by bound optics. The condition number of the system matrix is improved by using a preconditioner matrix. To calculate the preconditioner matrix, the system model is expressed in the frequency domain. The proposed method is simulated by using a compressive sensing algorithm called the two-step iterative shrinkage/thresholding algorithm. The results showed improved reconstruction fidelity with a certain number of iterations for high signal-to-noise ratio measurements. PMID:21633452
Tensor-Krylov methods for solving large-scale systems of nonlinear equations.
Bader, Brett William
2004-08-01
This paper develops and investigates iterative tensor methods for solving large-scale systems of nonlinear equations. Direct tensor methods for nonlinear equations have performed especially well on small, dense problems where the Jacobian matrix at the solution is singular or ill-conditioned, which may occur when approaching turning points, for example. This research extends direct tensor methods to large-scale problems by developing three tensor-Krylov methods that base each iteration upon a linear model augmented with a limited second-order term, which provides information lacking in a (nearly) singular Jacobian. The advantage of the new tensor-Krylov methods over existing large-scale tensor methods is their ability to solve the local tensor model to a specified accuracy, which produces a more accurate tensor step. The performance of these methods in comparison to Newton-GMRES and tensor-GMRES is explored on three Navier-Stokes fluid flow problems. The numerical results provide evidence that tensor-Krylov methods are generally more robust and more efficient than Newton-GMRES on some important and difficult problems. In addition, the results show that the new tensor-Krylov methods and tensor- GMRES each perform better in certain situations.
NASA Astrophysics Data System (ADS)
Calef, Matthew T.; Fichtl, Erin D.; Warsa, James S.; Berndt, Markus; Carlson, Neil N.
2013-04-01
We compare a variant of Anderson Mixing with the Jacobian-Free Newton-Krylov and Broyden methods applied to an instance of the k-eigenvalue formulation of the linear Boltzmann transport equation. We present evidence that one variant of Anderson Mixing finds solutions in the fewest number of iterations. We examine and strengthen theoretical results of Anderson Mixing applied to linear problems.
Manifold learning-based subspace distance for machinery damage assessment
NASA Astrophysics Data System (ADS)
Sun, Chuang; Zhang, Zhousuo; He, Zhengjia; Shen, Zhongjie; Chen, Binqiang
2016-03-01
Damage assessment is very meaningful to keep safety and reliability of machinery components, and vibration analysis is an effective way to carry out the damage assessment. In this paper, a damage index is designed by performing manifold distance analysis on vibration signal. To calculate the index, vibration signal is collected firstly, and feature extraction is carried out to obtain statistical features that can capture signal characteristics comprehensively. Then, manifold learning algorithm is utilized to decompose feature matrix to be a subspace, that is, manifold subspace. The manifold learning algorithm seeks to keep local relationship of the feature matrix, which is more meaningful for damage assessment. Finally, Grassmann distance between manifold subspaces is defined as a damage index. The Grassmann distance reflecting manifold structure is a suitable metric to measure distance between subspaces in the manifold. The defined damage index is applied to damage assessment of a rotor and the bearing, and the result validates its effectiveness for damage assessment of machinery component.
Ischemic preconditioning protects against ischemic brain injury
Ma, Xiao-meng; Liu, Mei; Liu, Ying-ying; Ma, Li-li; Jiang, Ying; Chen, Xiao-hong
2016-01-01
In this study, we hypothesized that an increase in integrin αvβ3 and its co-activator vascular endothelial growth factor play important neuroprotective roles in ischemic injury. We performed ischemic preconditioning with bilateral common carotid artery occlusion for 5 minutes in C57BL/6J mice. This was followed by ischemic injury with bilateral common carotid artery occlusion for 30 minutes. The time interval between ischemic preconditioning and lethal ischemia was 48 hours. Histopathological analysis showed that ischemic preconditioning substantially diminished damage to neurons in the hippocampus 7 days after ischemia. Evans Blue dye assay showed that ischemic preconditioning reduced damage to the blood-brain barrier 24 hours after ischemia. This demonstrates the neuroprotective effect of ischemic preconditioning. Western blot assay revealed a significant reduction in protein levels of integrin αvβ3, vascular endothelial growth factor and its receptor in mice given ischemic preconditioning compared with mice not given ischemic preconditioning 24 hours after ischemia. These findings suggest that the neuroprotective effect of ischemic preconditioning is associated with lower integrin αvβ3 and vascular endothelial growth factor levels in the brain following ischemia. PMID:27335560
Ischemic preconditioning protects against ischemic brain injury.
Ma, Xiao-Meng; Liu, Mei; Liu, Ying-Ying; Ma, Li-Li; Jiang, Ying; Chen, Xiao-Hong
2016-05-01
In this study, we hypothesized that an increase in integrin αvβ3 and its co-activator vascular endothelial growth factor play important neuroprotective roles in ischemic injury. We performed ischemic preconditioning with bilateral common carotid artery occlusion for 5 minutes in C57BL/6J mice. This was followed by ischemic injury with bilateral common carotid artery occlusion for 30 minutes. The time interval between ischemic preconditioning and lethal ischemia was 48 hours. Histopathological analysis showed that ischemic preconditioning substantially diminished damage to neurons in the hippocampus 7 days after ischemia. Evans Blue dye assay showed that ischemic preconditioning reduced damage to the blood-brain barrier 24 hours after ischemia. This demonstrates the neuroprotective effect of ischemic preconditioning. Western blot assay revealed a significant reduction in protein levels of integrin αvβ3, vascular endothelial growth factor and its receptor in mice given ischemic preconditioning compared with mice not given ischemic preconditioning 24 hours after ischemia. These findings suggest that the neuroprotective effect of ischemic preconditioning is associated with lower integrin αvβ3 and vascular endothelial growth factor levels in the brain following ischemia. PMID:27335560
40 CFR 80.52 - Vehicle preconditioning.
Code of Federal Regulations, 2013 CFR
2013-07-01
... accordance with the “General vehicle handling requirements” per 40 CFR 86.132-96, up to and including the completion of the hot start exhaust test. (b) The preconditioning procedure prescribed at 40 CFR 86.132-96... 40 Protection of Environment 17 2013-07-01 2013-07-01 false Vehicle preconditioning. 80.52...
Identifying Optimal Measurement Subspace for the Ensemble Kalman Filter
Zhou, Ning; Huang, Zhenyu; Welch, Greg; Zhang, J.
2012-05-24
To reduce the computational load of the ensemble Kalman filter while maintaining its efficacy, an optimization algorithm based on the generalized eigenvalue decomposition method is proposed for identifying the most informative measurement subspace. When the number of measurements is large, the proposed algorithm can be used to make an effective tradeoff between computational complexity and estimation accuracy. This algorithm also can be extended to other Kalman filters for measurement subspace selection.
Object classification using local subspace projection
NASA Astrophysics Data System (ADS)
Nealy, Jennifer; Muise, Robert
2011-06-01
We consider the problem of object classification from image data. Significant challenges are presented when objects can be imaged from different view angles and have different distortions. For example, a vehicle will appear completely different depending on the viewing angle of the sensor but must still be classified as the same vehicle. In regards to face recognition, a person may have a variety of facial expressions and a pattern recognition algorithm would need to account for these distortions. Traditional algorithms such as PCA filters are linear in nature and cannot account for the underlying non-linear structure which characterizes an object. We examine nonlinear manifold techniques applied to the pattern recognition problem. One mathematical construct receiving significant research attention is diffusion maps, whereby the underlying training data are remapped so that Euclidean distance in the mapped data is equivalent to the manifold distance of the original dataset. This technique has been used successfully for applications such as data organization, noise filtering, and anomaly detection with only limited experiments with object classification. For very large datasets (size N), pattern classification with diffusion maps becomes rather onerous as there is a requirement for the eigenvectors of an NxN matrix. We characterize the performance of a 40 person facial recognition problem with standard K-NN classifier, a diffusion distance classifier, and standard PCA. We then develop a local subspace projection algorithm which approximates the diffusion distance without the prohibitive computations and shows comparable classification performance.
Application of Subspace Clustering in DNA Sequence Analysis.
Wallace, Tim; Sekmen, Ali; Wang, Xiaofei
2015-10-01
Identification and clustering of orthologous genes plays an important role in developing evolutionary models such as validating convergent and divergent phylogeny and predicting functional proteins in newly sequenced species of unverified nucleotide protein mappings. Here, we introduce an application of subspace clustering as applied to orthologous gene sequences and discuss the initial results. The working hypothesis is based upon the concept that genetic changes between nucleotide sequences coding for proteins among selected species and groups may lie within a union of subspaces for clusters of the orthologous groups. Estimates for the subspace dimensions were computed for a small population sample. A series of experiments was performed to cluster randomly selected sequences. The experimental design allows for both false positives and false negatives, and estimates for the statistical significance are provided. The clustering results are consistent with the main hypothesis. A simple random mutation binary tree model is used to simulate speciation events that show the interdependence of the subspace rank versus time and mutation rates. The simple mutation model is found to be largely consistent with the observed subspace clustering singular value results. Our study indicates that the subspace clustering method may be applied in orthology analysis. PMID:26162018
Preconditioning Strategy in Stem Cell Transplantation Therapy
Yu, Shan Ping; Wei, Zheng; Wei, Ling
2013-01-01
Stem cell transplantation therapy has emerged as a promising regenerative medicine for ischemic stroke and other neurodegenerative disorders. However, many issues and problems remain to be resolved before successful clinical applications of the cell-based therapy. To this end, some recent investigations have sought to benefit from well-known mechanisms of ischemic/hypoxic preconditioning. Ischemic/hypoxic preconditioning activates endogenous defense mechanisms that show marked protective effects against multiple insults found in ischemic stroke and other acute attacks. As in many other cell types, a sub-lethal hypoxic exposure significantly increases the tolerance and regenerative properties of stem cells and progenitor cells. So far, a variety of preconditioning triggers have been tested on different stem cells and progenitor cells. Preconditioned stem cells and progenitors generally show much better cell survival, increased neuronal differentiation, enhanced paracrine effects leading to increased trophic support, and improved homing to the lesion site. Transplantation of preconditioned cells helps to suppress inflammatory factors and immune responses, and promote functional recovery. Although the preconditioning strategy in stem cell therapy is still an emerging research area, accumulating information from reports over the last few years already indicates it as an attractive, if not essential, prerequisite for transplanted cells. It is expected that stem cell preconditioning and its clinical applications will attract more attention in both the basic research field of preconditioning as well as in the field of stem cell translational research. This review summarizes the most important findings in this active research area, covering the preconditioning triggers, potential mechanisms, mediators, and functional benefits for stem cell transplant therapy. PMID:23914259
Global and Local Sparse Subspace Optimization for Motion Segmentation
NASA Astrophysics Data System (ADS)
Yang, M. Ying; Feng, S.; Ackermann, H.; Rosenhahn, B.
2015-08-01
In this paper, we propose a new framework for segmenting feature-based moving objects under affine subspace model. Since the feature trajectories in practice are high-dimensional and contain a lot of noise, we firstly apply the sparse PCA to represent the original trajectories with a low-dimensional global subspace, which consists of the orthogonal sparse principal vectors. Subsequently, the local subspace separation will be achieved via automatically searching the sparse representation of the nearest neighbors for each projected data. In order to refine the local subspace estimation result, we propose an error estimation to encourage the projected data that span a same local subspace to be clustered together. In the end, the segmentation of different motions is achieved through the spectral clustering on an affinity matrix, which is constructed with both the error estimation and sparse neighbors optimization. We test our method extensively and compare it with state-of-the-art methods on the Hopkins 155 dataset. The results show that our method is comparable with the other motion segmentation methods, and in many cases exceed them in terms of precision and computation time.
Parallel Newton-Krylov-Schwarz algorithms for the transonic full potential equation
NASA Technical Reports Server (NTRS)
Cai, Xiao-Chuan; Gropp, William D.; Keyes, David E.; Melvin, Robin G.; Young, David P.
1996-01-01
We study parallel two-level overlapping Schwarz algorithms for solving nonlinear finite element problems, in particular, for the full potential equation of aerodynamics discretized in two dimensions with bilinear elements. The overall algorithm, Newton-Krylov-Schwarz (NKS), employs an inexact finite-difference Newton method and a Krylov space iterative method, with a two-level overlapping Schwarz method as a preconditioner. We demonstrate that NKS, combined with a density upwinding continuation strategy for problems with weak shocks, is robust and, economical for this class of mixed elliptic-hyperbolic nonlinear partial differential equations, with proper specification of several parameters. We study upwinding parameters, inner convergence tolerance, coarse grid density, subdomain overlap, and the level of fill-in in the incomplete factorization, and report their effect on numerical convergence rate, overall execution time, and parallel efficiency on a distributed-memory parallel computer.
Newton-Krylov-Schwarz algorithms for the 2D full potential equation
Cai, Xiao-Chuan; Gropp, W.D.; Keyes, D.E.
1996-12-31
We study parallel two-level overlapping Schwarz algorithms for solving nonlinear finite element problems, in particular, for the full potential equation of aerodynamics discretized in two dimensions with bilinear elements. The main algorithm, Newton-Krylov-Schwarz (NKS), employs an inexact finite-difference Newton method and a Krylov space iterative method, with a two-level overlapping Schwarz method as a preconditioner. We demonstrate that NKS, combined with a density upwinding continuation strategy for problems with weak shocks, can be made robust for this class of mixed elliptic-hyperbolic nonlinear partial differential equations, with proper specification of several parameters. We study upwinding parameters, inner convergence tolerance, coarse grid density, subdomain overlap, and the level of fill-in in the incomplete factorization, and report favorable choices for numerical convergence rate and overall execution time on a distributed-memory parallel computer.
40 CFR 80.52 - Vehicle preconditioning.
Code of Federal Regulations, 2010 CFR
2010-07-01
... accordance with the “General vehicle handling requirements” per 40 CFR 86.132-96, up to and including the completion of the hot start exhaust test. (b) The preconditioning procedure prescribed at 40 CFR...
40 CFR 80.52 - Vehicle preconditioning.
Code of Federal Regulations, 2011 CFR
2011-07-01
... accordance with the “General vehicle handling requirements” per 40 CFR 86.132-96, up to and including the completion of the hot start exhaust test. (b) The preconditioning procedure prescribed at 40 CFR...
Laser thermal preconditioning enhances dermal wound repair
NASA Astrophysics Data System (ADS)
Wilmink, Gerald J.; Carter, Terry; Davidson, Jeffrey M.; Jansen, E. Duco
2008-02-01
Preconditioning tissues with an initial mild thermal stress, thereby eliciting a stress response, can serve to protect tissue from subsequent stresses. Patients at risk for impaired healing, such as diabetics, can benefit from therapeutic methods which enhance wound repair. We present a laser thermal preconditioning protocol that accelerates cutaneous wound repair in a murine model. A pulsed diode laser (λ = 1.86 μm, τ p = 2 ms, 50 Hz, H = 7.64 mJ/cm2) was used to precondition mouse skin before incisional wounds were made. The preconditioning protocol was optimized in vitro and in vivo using hsp70 expression, cell viability, and temperature measurements as benchmarks. Hsp70 expression was non-invasively monitored using a transgenic mouse strain with the hsp70 promoter driving luciferase expression. Tissue temperature recordings were acquired in real time using an infrared camera. Wound repair was assessed by measuring hsp70 expression, biomechanical properties, and wound histology for up to 24 d. Bioluminescence (BLI) was monitored with the IVIS 200 System (Xenogen) and tensile properties with a tensiometer (BTC-2000). The in vivo BLI studies indicated that the optimized laser preconditioning protocol increased hsp70 expression by 15-fold. The tensiometer data revealed that laser preconditioned wounds are ~40% stronger than control wounds at 10 days post surgery. Similar experiments in a diabetic mouse model also enhanced wound repair strength. These results indicate that 1) noninvasive imaging methods can aid in the optimization of novel laser preconditioning methods; 2) that optimized preconditioning with a 1.86 μm diode laser enhances early wound repair.
A Newton-Krylov Solver for Implicit Solution of Hydrodynamics in Core Collapse Supernovae
Reynolds, D R; Swesty, F D; Woodward, C S
2008-06-12
This paper describes an implicit approach and nonlinear solver for solution of radiation-hydrodynamic problems in the context of supernovae and proto-neutron star cooling. The robust approach applies Newton-Krylov methods and overcomes the difficulties of discontinuous limiters in the discretized equations and scaling of the equations over wide ranges of physical behavior. We discuss these difficulties, our approach for overcoming them, and numerical results demonstrating accuracy and efficiency of the method.
Bradykinin mediates cardiac preconditioning at a distance.
Schoemaker, R G; van Heijningen, C L
2000-05-01
Preconditioning the heart by brief coronary (CAO) or mesenteric artery occlusion (MAO) can protect against damage during subsequent prolonged CAO and reperfusion. The role of bradykinin (BK) in remote cardiac preconditioning by MAO is investigated by antagonizing the BK B(2) receptor [Hoechst 140 (HOE-140)] or simulating local BK release by mesenteric intra-arterial infusion. Anesthetized male Wistar rats (n = 6-8) were treated with HOE-140 or saline before starting the preconditioning protocol, CAO, MAO, or non-preconditioned control. Infarct size related to risk area [ratio of infarct area to area at risk (IA/AR)] was determined after 3 h of reperfusion following a 60-min CAO. IA/AR was 62 +/- 5% in controls and not affected by HOE-140 (58 +/- 6%). CAO as well as MAO significantly protected the heart (IA/AR, 37 +/- 3 and 35 +/- 5%), which was prevented by HOE-140 (IA/AR, 71 +/- 6 and 65 +/- 7%, respectively). Brief intramesenteric BK infusion mimicked MAO (IA/AR, 26 +/- 3%). Pretreatment with hexamethonium could abolish this protection (IA/AR, 67 +/- 4%). These data indicate an important role for BK in remote preconditioning by MAO. Results support the hypothesis that remote preconditioning acts through sensory nerve stimulation in the ischemic organ. PMID:10775135
Selective control of the symmetric Dicke subspace in trapped ions
Lopez, C. E.; Retamal, J. C.; Solano, E.
2007-09-15
We propose a method of manipulating selectively the symmetric Dicke subspace in the internal degrees of freedom of N trapped ions. We show that the direct access to ionic-motional subspaces, based on a suitable tuning of motion-dependent ac Stark shifts, induces a two-level dynamics involving previously selected ionic Dicke states. In this manner, it is possible to produce, sequentially and unitarily, ionic Dicke states with increasing excitation number. Moreover, we propose a probabilistic technique to produce directly any ionic Dicke state assuming suitable initial conditions.
Computational Complexity of Subspace Detectors and Matched Field Processing
Harris, D B
2010-12-01
Subspace detectors implement a correlation type calculation on a continuous (network or array) data stream [Harris, 2006]. The difference between subspace detectors and correlators is that the former projects the data in a sliding observation window onto a basis of template waveforms that may have a dimension (d) greater than one, and the latter projects the data onto a single waveform template. A standard correlation detector can be considered to be a degenerate (d=1) form of a subspace detector. Figure 1 below shows a block diagram for the standard formulation of a subspace detector. The detector consists of multiple multichannel correlators operating on a continuous data stream. The correlation operations are performed with FFTs in an overlap-add approach that allows the stream to be processed in uniform, consecutive, contiguous blocks. Figure 1 is slightly misleading for a calculation of computational complexity, as it is possible, when treating all channels with the same weighting (as shown in the figure), to perform the indicated summations in the multichannel correlators before the inverse FFTs and to get by with a single inverse FFT and overlap add calculation per multichannel correlator. In what follows, we make this simplification.
Decoherence free subspaces of a quantum Markov semigroup
Agredo, Julián; Fagnola, Franco; Rebolledo, Rolando
2014-11-15
We give a full characterisation of decoherence free subspaces of a given quantum Markov semigroup with generator in a generalised Lindbald form which is valid also for infinite-dimensional systems. Our results, extending those available in the literature concerning finite-dimensional systems, are illustrated by some examples.
Minimal residual method stronger than polynomial preconditioning
Faber, V.; Joubert, W.; Knill, E.
1994-12-31
Two popular methods for solving symmetric and nonsymmetric systems of equations are the minimal residual method, implemented by algorithms such as GMRES, and polynomial preconditioning methods. In this study results are given on the convergence rates of these methods for various classes of matrices. It is shown that for some matrices, such as normal matrices, the convergence rates for GMRES and for the optimal polynomial preconditioning are the same, and for other matrices such as the upper triangular Toeplitz matrices, it is at least assured that if one method converges then the other must converge. On the other hand, it is shown that matrices exist for which restarted GMRES always converges but any polynomial preconditioning of corresponding degree makes no progress toward the solution for some initial error. The implications of these results for these and other iterative methods are discussed.
Preconditioning the Helmholtz Equation for Rigid Ducts
NASA Technical Reports Server (NTRS)
Baumeister, Kenneth J.; Kreider, Kevin L.
1998-01-01
An innovative hyperbolic preconditioning technique is developed for the numerical solution of the Helmholtz equation which governs acoustic propagation in ducts. Two pseudo-time parameters are used to produce an explicit iterative finite difference scheme. This scheme eliminates the large matrix storage requirements normally associated with numerical solutions to the Helmholtz equation. The solution procedure is very fast when compared to other transient and steady methods. Optimization and an error analysis of the preconditioning factors are present. For validation, the method is applied to sound propagation in a 2D semi-infinite hard wall duct.
NASA Astrophysics Data System (ADS)
Hayes, Charles E.; McClellan, James H.; Scott, Waymond R.; Kerr, Andrew J.
2016-05-01
This work introduces two advances in wide-band electromagnetic induction (EMI) processing: a novel adaptive matched filter (AMF) and matched subspace detection methods. Both advances make use of recent work with a subspace SVD approach to separating the signal, soil, and noise subspaces of the frequency measurements The proposed AMF provides a direct approach to removing the EMI self-response while improving the signal to noise ratio of the data. Unlike previous EMI adaptive downtrack filters, this new filter will not erroneously optimize the EMI soil response instead of the EMI target response because these two responses are projected into separate frequency subspaces. The EMI detection methods in this work elaborate on how the signal and noise subspaces in the frequency measurements are ideal for creating the matched subspace detection (MSD) and constant false alarm rate matched subspace detection (CFAR) metrics developed by Scharf The CFAR detection metric has been shown to be the uniformly most powerful invariant detector.
NASA Astrophysics Data System (ADS)
Aguiar, Manuela A. D.; Dias, Ana Paula S.
2014-12-01
Coupled cell systems are networks of dynamical systems (the cells), where the links between the cells are described through the network structure, the coupled cell network. Synchrony subspaces are spaces defined in terms of equalities of certain cell coordinates that are flow-invariant for all coupled cell systems associated with a given network structure. The intersection of synchrony subspaces of a network is also a synchrony subspace of the network. It follows, then, that, given a coupled cell network, its set of synchrony subspaces, taking the inclusion partial order relation, forms a lattice. In this paper we show how to obtain the lattice of synchrony subspaces for a general network and present an algorithm that generates that lattice. We prove that this problem is reduced to obtain the lattice of synchrony subspaces for regular networks. For a regular network we obtain the lattice of synchrony subspaces based on the eigenvalue structure of the network adjacency matrix.
Solving Nonlinear Solid Mechanics Problems with the Jacobian-Free Newton Krylov Method
J. D. Hales; S. R. Novascone; R. L. Williamson; D. R. Gaston; M. R. Tonks
2012-06-01
The solution of the equations governing solid mechanics is often obtained via Newton's method. This approach can be problematic if the determination, storage, or solution cost associated with the Jacobian is high. These challenges are magnified for multiphysics applications with many coupled variables. Jacobian-free Newton-Krylov (JFNK) methods avoid many of the difficulties associated with the Jacobian by using a finite difference approximation. BISON is a parallel, object-oriented, nonlinear solid mechanics and multiphysics application that leverages JFNK methods. We overview JFNK, outline the capabilities of BISON, and demonstrate the effectiveness of JFNK for solid mechanics and solid mechanics coupled to other PDEs using a series of demonstration problems.
Using generalized Cayley transformations within an inexact rational Krylov sequence method.
Lehoucq, R. B.; Meerbergen, K.; Mathematics and Computer Science; Utrecht Univ.
1999-01-01
The rational Krylov sequence (RKS) method is a generalization of Arnoldi's method. It constructs an orthogonal reduction of a matrix pencil into an upper Hessenberg pencil. The RKS method is useful when the matrix pencil may be efficiently factored. This article considers approximately solving the resulting linear systems with iterative methods. We show that a Cayley transformation leads to a more efficient and robust eigensolver than the usual shift-invert transformation when the linear systems are solved inexactly within the RKS method. A relationship with the recently introduced Jacobi--Davidson method is also established.
Preconditioning matrices for Chebyshev derivative operators
NASA Technical Reports Server (NTRS)
Rothman, Ernest E.
1986-01-01
The problem of preconditioning the matrices arising from pseudo-spectral Chebyshev approximations of first order operators is considered in both one and two dimensions. In one dimension a preconditioner represented by a full matrix which leads to preconditioned eigenvalues that are real, positive, and lie between 1 and pi/2, is already available. Since there are cases in which it is not computationally convenient to work with such a preconditioner, a large number of preconditioners were studied which were more sparse (in particular three and four diagonal matrices). The eigenvalues of such preconditioned matrices are compared. The results were applied to the problem of finding the steady state solution to an equation of the type u sub t = u sub x + f, where the Chebyshev collocation is used for the spatial variable and time discretization is performed by the Richardson method. In two dimensions different preconditioners are proposed for the matrix which arises from the pseudo-spectral discretization of the steady state problem. Results are given for the CPU time and the number of iterations using a Richardson iteration method for the unpreconditioned and preconditioned cases.
Revealing Preconditions for Trustful Collaboration in CSCL
ERIC Educational Resources Information Center
Gerdes, Anne
2010-01-01
This paper analyses preconditions for trust in virtual learning environments. The concept of trust is discussed with reference to cases reporting trust in cyberspace and through a philosophical clarification holding that trust in the form of self-surrender is a common characteristic of all human co-existence. In virtual learning environments,…
Resveratrol and ischemic preconditioning in the brain.
Raval, Ami P; Lin, Hung Wen; Dave, Kunjan R; Defazio, R Anthony; Della Morte, David; Kim, Eun Joo; Perez-Pinzon, Miguel A
2008-01-01
Cardiovascular pathologies in the French are not prevalent despite high dietary saturated fat consumption. This is commonly referred to as the "French Paradox" attributing its anti-lipidemic effects to moderate consumption of red wine. Resveratrol, a phytoalexin found in red wine, is currently the focus of intense research both in the cardiovascular system and the brain. Current research suggests resveratrol may enhance prognosis of neurological disorders such as, Parkinson's, Huntington's, Alzheimer's diseases and stroke. The beneficial effects of resveratrol include: antioxidation, free radical scavenger, and modulation of neuronal energy homeostasis and glutamatergic receptors/ion channels. Resveratrol directly increases sirtuin 1 (SIRT1) activity, a NAD(+) (oxidized form of nicotinamide adenine dinucleotide)-dependent histone deacetylase related to increased lifespan in various species similar to calorie restriction. We recently demonstrated that brief resveratrol pretreatment conferred neuroprotection against cerebral ischemia via SIRT1 activation. This neuroprotective effect produced by resveratrol was similar to ischemic preconditioning-induced neuroprotection, which protects against lethal ischemic insults in the brain and other organ systems. Inhibition of SIRT1 abolished ischemic preconditioning-induced neuroprotection in CA1 region of the hippocampus. Since resveratrol and ischemic preconditioning-induced neuroprotection require activation of SIRT1, this common signaling pathway may provide targeted therapeutic treatment modalities as it relates to stroke and other brain pathologies. In this review, we will examine common signaling pathways, cellular targets of resveratrol, and ischemic preconditioning-induced neuroprotection as it relates to the brain. PMID:18537630
Health and Nutrition: Preconditions for Educational Achievement.
ERIC Educational Resources Information Center
Negussie, Birgit
This paper discusses the importance of maternal and infant health for children's educational achievement. Education, health, and nutrition are so closely related that changes in one causes changes in the others. Improvement of maternal and preschooler health and nutrition is a precondition for improved educational achievement. Although parental…
40 CFR 1065.518 - Engine preconditioning.
Code of Federal Regulations, 2014 CFR
2014-07-01
..., such as with a diesel engine that relies on urea-based selective catalytic reduction. Note that § 1065... cycle specified in 40 CFR 1039.505(b)(1), the second half of the cycle consists of modes three through... 40 Protection of Environment 33 2014-07-01 2014-07-01 false Engine preconditioning....
Smooth local subspace projection for nonlinear noise reduction
Chelidze, David
2014-03-15
Many nonlinear or chaotic time series exhibit an innate broad spectrum, which makes noise reduction difficult. Local projective noise reduction is one of the most effective tools. It is based on proper orthogonal decomposition (POD) and works for both map-like and continuously sampled time series. However, POD only looks at geometrical or topological properties of data and does not take into account the temporal characteristics of time series. Here, we present a new smooth projective noise reduction method. It uses smooth orthogonal decomposition (SOD) of bundles of reconstructed short-time trajectory strands to identify smooth local subspaces. Restricting trajectories to these subspaces imposes temporal smoothness on the filtered time series. It is shown that SOD-based noise reduction significantly outperforms the POD-based method for continuously sampled noisy time series.
Low complex subspace minimum variance beamformer for medical ultrasound imaging.
Deylami, Ali Mohades; Asl, Babak Mohammadzadeh
2016-03-01
Minimum variance (MV) beamformer enhances the resolution and contrast in the medical ultrasound imaging at the expense of higher computational complexity with respect to the non-adaptive delay-and-sum beamformer. The major complexity arises from the estimation of the L×L array covariance matrix using spatial averaging, which is required to more accurate estimation of the covariance matrix of correlated signals, and inversion of it, which is required for calculating the MV weight vector which are as high as O(L(2)) and O(L(3)), respectively. Reducing the number of array elements decreases the computational complexity but degrades the imaging resolution. In this paper, we propose a subspace MV beamformer which preserves the advantages of the MV beamformer with lower complexity. The subspace MV neglects some rows of the array covariance matrix instead of reducing the array size. If we keep η rows of the array covariance matrix which leads to a thin non-square matrix, the weight vector of the subspace beamformer can be achieved in the same way as the MV obtains its weight vector with lower complexity as high as O(η(2)L). More calculations would be saved because an η×L covariance matrix must be estimated instead of a L×L. We simulated a wire targets phantom and a cyst phantom to evaluate the performance of the proposed beamformer. The results indicate that we can keep about 16 from 43 rows of the array covariance matrix which reduces the order of complexity to 14% while the image resolution is still comparable to that of the standard MV beamformer. We also applied the proposed method to an experimental RF data and showed that the subspace MV beamformer performs like the standard MV with lower computational complexity. PMID:26678788
Condition number estimation of preconditioned matrices.
Kushida, Noriyuki
2015-01-01
The present paper introduces a condition number estimation method for preconditioned matrices. The newly developed method provides reasonable results, while the conventional method which is based on the Lanczos connection gives meaningless results. The Lanczos connection based method provides the condition numbers of coefficient matrices of systems of linear equations with information obtained through the preconditioned conjugate gradient method. Estimating the condition number of preconditioned matrices is sometimes important when describing the effectiveness of new preconditionerers or selecting adequate preconditioners. Operating a preconditioner on a coefficient matrix is the simplest method of estimation. However, this is not possible for large-scale computing, especially if computation is performed on distributed memory parallel computers. This is because, the preconditioned matrices become dense, even if the original matrices are sparse. Although the Lanczos connection method can be used to calculate the condition number of preconditioned matrices, it is not considered to be applicable to large-scale problems because of its weakness with respect to numerical errors. Therefore, we have developed a robust and parallelizable method based on Hager's method. The feasibility studies are curried out for the diagonal scaling preconditioner and the SSOR preconditioner with a diagonal matrix, a tri-daigonal matrix and Pei's matrix. As a result, the Lanczos connection method contains around 10% error in the results even with a simple problem. On the other hand, the new method contains negligible errors. In addition, the newly developed method returns reasonable solutions when the Lanczos connection method fails with Pei's matrix, and matrices generated with the finite element method. PMID:25816331
Condition Number Estimation of Preconditioned Matrices
Kushida, Noriyuki
2015-01-01
The present paper introduces a condition number estimation method for preconditioned matrices. The newly developed method provides reasonable results, while the conventional method which is based on the Lanczos connection gives meaningless results. The Lanczos connection based method provides the condition numbers of coefficient matrices of systems of linear equations with information obtained through the preconditioned conjugate gradient method. Estimating the condition number of preconditioned matrices is sometimes important when describing the effectiveness of new preconditionerers or selecting adequate preconditioners. Operating a preconditioner on a coefficient matrix is the simplest method of estimation. However, this is not possible for large-scale computing, especially if computation is performed on distributed memory parallel computers. This is because, the preconditioned matrices become dense, even if the original matrices are sparse. Although the Lanczos connection method can be used to calculate the condition number of preconditioned matrices, it is not considered to be applicable to large-scale problems because of its weakness with respect to numerical errors. Therefore, we have developed a robust and parallelizable method based on Hager’s method. The feasibility studies are curried out for the diagonal scaling preconditioner and the SSOR preconditioner with a diagonal matrix, a tri-daigonal matrix and Pei’s matrix. As a result, the Lanczos connection method contains around 10% error in the results even with a simple problem. On the other hand, the new method contains negligible errors. In addition, the newly developed method returns reasonable solutions when the Lanczos connection method fails with Pei’s matrix, and matrices generated with the finite element method. PMID:25816331
Relations Among Some Low-Rank Subspace Recovery Models.
Zhang, Hongyang; Lin, Zhouchen; Zhang, Chao; Gao, Junbin
2015-09-01
Recovering intrinsic low-dimensional subspaces from data distributed on them is a key preprocessing step to many applications. In recent years, a lot of work has modeled subspace recovery as low-rank minimization problems. We find that some representative models, such as robust principal component analysis (R-PCA), robust low-rank representation (R-LRR), and robust latent low-rank representation (R-LatLRR), are actually deeply connected. More specifically, we discover that once a solution to one of the models is obtained, we can obtain the solutions to other models in closed-form formulations. Since R-PCA is the simplest, our discovery makes it the center of low-rank subspace recovery models. Our work has two important implications. First, R-PCA has a solid theoretical foundation. Under certain conditions, we could find globally optimal solutions to these low-rank models at an overwhelming probability, although these models are nonconvex. Second, we can obtain significantly faster algorithms for these models by solving R-PCA first. The computation cost can be further cut by applying low-complexity randomized algorithms, for example, our novel l2,1 filtering algorithm, to R-PCA. Although for the moment the formal proof of our l2,1 filtering algorithm is not yet available, experiments verify the advantages of our algorithm over other state-of-the-art methods based on the alternating direction method. PMID:26161818
Subspace-based Inverse Uncertainty Quantification for Nuclear Data Assessment
NASA Astrophysics Data System (ADS)
Khuwaileh, B. A.; Abdel-Khalik, H. S.
2015-01-01
Safety analysis and design optimization depend on the accurate prediction of various reactor attributes. Predictions can be enhanced by reducing the uncertainty associated with the attributes of interest. An inverse problem can be defined and solved to assess the sources of uncertainty, and experimental effort can be subsequently directed to further improve the uncertainty associated with these sources. In this work a subspace-based algorithm for inverse sensitivity/uncertainty quantification (IS/UQ) has been developed to enable analysts account for all sources of nuclear data uncertainties in support of target accuracy assessment-type analysis. An approximate analytical solution of the optimization problem is used to guide the search for the dominant uncertainty subspace. By limiting the search to a subspace, the degrees of freedom available for the optimization search are significantly reduced. A quarter PWR fuel assembly is modeled and the accuracy of the multiplication factor and the fission reaction rate are used as reactor attributes whose uncertainties are to be reduced. Numerical experiments are used to demonstrate the computational efficiency of the proposed algorithm. Our ongoing work is focusing on extending the proposed algorithm to account for various forms of feedback, e.g., thermal-hydraulics and depletion effects.
Subspace-based Inverse Uncertainty Quantification for Nuclear Data Assessment
Khuwaileh, B.A. Abdel-Khalik, H.S.
2015-01-15
Safety analysis and design optimization depend on the accurate prediction of various reactor attributes. Predictions can be enhanced by reducing the uncertainty associated with the attributes of interest. An inverse problem can be defined and solved to assess the sources of uncertainty, and experimental effort can be subsequently directed to further improve the uncertainty associated with these sources. In this work a subspace-based algorithm for inverse sensitivity/uncertainty quantification (IS/UQ) has been developed to enable analysts account for all sources of nuclear data uncertainties in support of target accuracy assessment-type analysis. An approximate analytical solution of the optimization problem is used to guide the search for the dominant uncertainty subspace. By limiting the search to a subspace, the degrees of freedom available for the optimization search are significantly reduced. A quarter PWR fuel assembly is modeled and the accuracy of the multiplication factor and the fission reaction rate are used as reactor attributes whose uncertainties are to be reduced. Numerical experiments are used to demonstrate the computational efficiency of the proposed algorithm. Our ongoing work is focusing on extending the proposed algorithm to account for various forms of feedback, e.g., thermal-hydraulics and depletion effects.
Improved Stochastic Subspace System Identification for Structural Health Monitoring
NASA Astrophysics Data System (ADS)
Chang, Chia-Ming; Loh, Chin-Hsiung
2015-07-01
Structural health monitoring acquires structural information through numerous sensor measurements. Vibrational measurement data render the dynamic characteristics of structures to be extracted, in particular of the modal properties such as natural frequencies, damping, and mode shapes. The stochastic subspace system identification has been recognized as a power tool which can present a structure in the modal coordinates. To obtain qualitative identified data, this tool needs to spend computational expense on a large set of measurements. In study, a stochastic system identification framework is proposed to improve the efficiency and quality of the conventional stochastic subspace system identification. This framework includes 1) measured signal processing, 2) efficient space projection, 3) system order selection, and 4) modal property derivation. The measured signal processing employs the singular spectrum analysis algorithm to lower the noise components as well as to present a data set in a reduced dimension. The subspace is subsequently derived from the data set presented in a delayed coordinate. With the proposed order selection criteria, the number of structural modes is determined, resulting in the modal properties. This system identification framework is applied to a real-world bridge for exploring the feasibility in real-time applications. The results show that this improved system identification method significantly decreases computational time, while qualitative modal parameters are still attained.
Universal Subspaces for Local Unitary Groups of Fermionic Systems
NASA Astrophysics Data System (ADS)
Chen, Lin; Chen, Jianxin; Đoković, Dragomir Ž.; Zeng, Bei
2015-01-01
Let be the N-fermion Hilbert space with M-dimensional single particle space V and 2 N ≤ M. We refer to the unitary group G of V as the local unitary (LU) group. We fix an orthonormal (o.n.) basis | v 1⟩,...,| v M > of V. Then the Slater determinants with i 1 < ... < i N form an o.n. basis of . Let be the subspace spanned by all such that the set { i 1,..., i N } contains no pair {2 k-1,2 k}, k an integer. We say that the are single occupancy states (with respect to the basis | v 1⟩,...,| v M ⟩). We prove that for N = 3 the subspace is universal, i.e., each G-orbit in meets , and that this is false for N > 3. If M is even, the well known BCS states are not LU-equivalent to any single occupancy state. Our main result is that for N = 3 and M even there is a universal subspace spanned by M( M-1)( M-5)/6 states . Moreover, the number M( M-1)( M-5)/6 is minimal.
Self-adjoint time operators and invariant subspaces
NASA Astrophysics Data System (ADS)
Gómez, Fernando
2008-02-01
The question of existence of self-adjoint time operators for unitary evolutions in classical and quantum mechanics is revisited on the basis of Halmos-Helson theory of invariant subspaces, Sz.-Nagy-Foiaş dilation theory and Misra-Prigogine-Courbage theory of irreversibility. It is shown that the existence of self-adjoint time operators is equivalent to the intertwining property of the evolution plus the existence of simply invariant subspaces or rigid operator-valued functions for its Sz.-Nagy-Foiaş functional model. Similar equivalent conditions are given in terms of intrinsic randomness in the context of statistical mechanics. The rest of the contents are mainly a unifying review of the subject scattered throughout an unconnected literature. A well-known extensive set of equivalent conditions is derived from the above results; such conditions are written in terms of Schrrdinger couples, the Weyl commutation relation, incoming and outgoing subspaces, innovation processes, Lax-Phillips scattering, translation and spectral representations, and spectral properties. Also the natural procedure dealing with symmetric time operators in standard quantum mechanics involving their self-adjoint extensions is illustrated by considering the quantum Aharonov-Bohm time-of-arrival operator.
Globalized Newton-Krylov-Schwarz Algorithms and Software for Parallel Implicit CFD
NASA Technical Reports Server (NTRS)
Gropp, W. D.; Keyes, D. E.; McInnes, L. C.; Tidriri, M. D.
1998-01-01
Implicit solution methods are important in applications modeled by PDEs with disparate temporal and spatial scales. Because such applications require high resolution with reasonable turnaround, "routine" parallelization is essential. The pseudo-transient matrix-free Newton-Krylov-Schwarz (Psi-NKS) algorithmic framework is presented as an answer. We show that, for the classical problem of three-dimensional transonic Euler flow about an M6 wing, Psi-NKS can simultaneously deliver: globalized, asymptotically rapid convergence through adaptive pseudo- transient continuation and Newton's method-, reasonable parallelizability for an implicit method through deferred synchronization and favorable communication-to-computation scaling in the Krylov linear solver; and high per- processor performance through attention to distributed memory and cache locality, especially through the Schwarz preconditioner. Two discouraging features of Psi-NKS methods are their sensitivity to the coding of the underlying PDE discretization and the large number of parameters that must be selected to govern convergence. We therefore distill several recommendations from our experience and from our reading of the literature on various algorithmic components of Psi-NKS, and we describe a freely available, MPI-based portable parallel software implementation of the solver employed here.
Krylov iterative methods and synthetic acceleration for transport in binary statistical media
Fichtl, Erin D; Warsa, James S; Prinja, Anil K
2008-01-01
In particle transport applications there are numerous physical constructs in which heterogeneities are randomly distributed. The quantity of interest in these problems is the ensemble average of the flux, or the average of the flux over all possible material 'realizations.' The Levermore-Pomraning closure assumes Markovian mixing statistics and allows a closed, coupled system of equations to be written for the ensemble averages of the flux in each material. Generally, binary statistical mixtures are considered in which there are two (homogeneous) materials and corresponding coupled equations. The solution process is iterative, but convergence may be slow as either or both materials approach the diffusion and/or atomic mix limits. A three-part acceleration scheme is devised to expedite convergence, particularly in the atomic mix-diffusion limit where computation is extremely slow. The iteration is first divided into a series of 'inner' material and source iterations to attenuate the diffusion and atomic mix error modes separately. Secondly, atomic mix synthetic acceleration is applied to the inner material iteration and S{sup 2} synthetic acceleration to the inner source iterations to offset the cost of doing several inner iterations per outer iteration. Finally, a Krylov iterative solver is wrapped around each iteration, inner and outer, to further expedite convergence. A spectral analysis is conducted and iteration counts and computing cost for the new two-step scheme are compared against those for a simple one-step iteration, to which a Krylov iterative method can also be applied.
Analysis of some large-scale nonlinear stochastic dynamic systems with subspace-EPC method
NASA Astrophysics Data System (ADS)
Er, GuoKang; Iu, VaiPan
2011-09-01
The probabilistic solutions to some nonlinear stochastic dynamic (NSD) systems with various polynomial types of nonlinearities in displacements are analyzed with the subspace-exponential polynomial closure (subspace-EPC) method. The space of the state variables of the large-scale nonlinear stochastic dynamic system excited by Gaussian white noises is separated into two subspaces. Both sides of the Fokker-Planck-Kolmogorov (FPK) equation corresponding to the NSD system are then integrated over one of the subspaces. The FPK equation for the joint probability density function of the state variables in the other subspace is formulated. Therefore, the FPK equations in low dimensions are obtained from the original FPK equation in high dimensions and the FPK equations in low dimensions are solvable with the exponential polynomial closure method. Examples about multi-degree-offreedom NSD systems with various polynomial types of nonlinearities in displacements are given to show the effectiveness of the subspace-EPC method in these cases.
A Hybrid Parallel Preconditioning Algorithm For CFD
NASA Technical Reports Server (NTRS)
Barth,Timothy J.; Tang, Wei-Pai; Kwak, Dochan (Technical Monitor)
1995-01-01
A new hybrid preconditioning algorithm will be presented which combines the favorable attributes of incomplete lower-upper (ILU) factorization with the favorable attributes of the approximate inverse method recently advocated by numerous researchers. The quality of the preconditioner is adjustable and can be increased at the cost of additional computation while at the same time the storage required is roughly constant and approximately equal to the storage required for the original matrix. In addition, the preconditioning algorithm suggests an efficient and natural parallel implementation with reduced communication. Sample calculations will be presented for the numerical solution of multi-dimensional advection-diffusion equations. The matrix solver has also been embedded into a Newton algorithm for solving the nonlinear Euler and Navier-Stokes equations governing compressible flow. The full paper will show numerous examples in CFD to demonstrate the efficiency and robustness of the method.
Preconditioning Stem Cells for In Vivo Delivery
Sart, Sébastien; Ma, Teng
2014-01-01
Abstract Stem cells have emerged as promising tools for the treatment of incurable neural and heart diseases and tissue damage. However, the survival of transplanted stem cells is reported to be low, reducing their therapeutic effects. The major causes of poor survival of stem cells in vivo are linked to anoikis, potential immune rejection, and oxidative damage mediating apoptosis. This review investigates novel methods and potential molecular mechanisms for stem cell preconditioning in vitro to increase their retention after transplantation in damaged tissues. Microenvironmental preconditioning (e.g., hypoxia, heat shock, and exposure to oxidative stress), aggregate formation, and hydrogel encapsulation have been revealed as promising strategies to reduce cell apoptosis in vivo while maintaining biological functions of the cells. Moreover, this review seeks to identify methods of optimizing cell dose preparation to enhance stem cell survival and therapeutic function after transplantation. PMID:25126478
M-step preconditioned conjugate gradient methods
NASA Technical Reports Server (NTRS)
Adams, L.
1983-01-01
Preconditioned conjugate gradient methods for solving sparse symmetric and positive finite systems of linear equations are described. Necessary and sufficient conditions are given for when these preconditioners can be used and an analysis of their effectiveness is given. Efficient computer implementations of these methods are discussed and results on the CYBER 203 and the Finite Element Machine under construction at NASA Langley Research Center are included.
On polynomial preconditioning for indefinite Hermitian matrices
NASA Technical Reports Server (NTRS)
Freund, Roland W.
1989-01-01
The minimal residual method is studied combined with polynomial preconditioning for solving large linear systems (Ax = b) with indefinite Hermitian coefficient matrices (A). The standard approach for choosing the polynomial preconditioners leads to preconditioned systems which are positive definite. Here, a different strategy is studied which leaves the preconditioned coefficient matrix indefinite. More precisely, the polynomial preconditioner is designed to cluster the positive, resp. negative eigenvalues of A around 1, resp. around some negative constant. In particular, it is shown that such indefinite polynomial preconditioners can be obtained as the optimal solutions of a certain two parameter family of Chebyshev approximation problems. Some basic results are established for these approximation problems and a Remez type algorithm is sketched for their numerical solution. The problem of selecting the parameters such that the resulting indefinite polynomial preconditioners speeds up the convergence of minimal residual method optimally is also addressed. An approach is proposed based on the concept of asymptotic convergence factors. Finally, some numerical examples of indefinite polynomial preconditioners are given.
Video background tracking and foreground extraction via L1-subspace updates
NASA Astrophysics Data System (ADS)
Pierantozzi, Michele; Liu, Ying; Pados, Dimitris A.; Colonnese, Stefania
2016-05-01
We consider the problem of online foreground extraction from compressed-sensed (CS) surveillance videos. A technically novel approach is suggested and developed by which the background scene is captured by an L1- norm subspace sequence directly in the CS domain. In contrast to conventional L2-norm subspaces, L1-norm subspaces are seen to offer significant robustness to outliers, disturbances, and rank selection. Subtraction of the L1-subspace tracked background leads then to effective foreground/moving objects extraction. Experimental studies included in this paper illustrate and support the theoretical developments.
Subspace-based analysis of the ERT inverse problem
NASA Astrophysics Data System (ADS)
Ben Hadj Miled, Mohamed Khames; Miller, Eric L.
2004-05-01
In a previous work, we proposed a source-type formulation to the electrical resistance tomography (ERT) problem. Specifically, we showed that inhomogeneities in the medium can be viewed as secondary sources embedded in the homogeneous background medium and located at positions associated with variation in electrical conductivity. Assuming a piecewise constant conductivity distribution, the support of equivalent sources is equal to the boundary of the inhomogeneity. The estimation of the anomaly shape takes the form of an inverse source-type problem. In this paper, we explore the use of subspace methods to localize the secondary equivalent sources associated with discontinuities in the conductivity distribution. Our first alternative is the multiple signal classification (MUSIC) algorithm which is commonly used in the localization of multiple sources. The idea is to project a finite collection of plausible pole (or dipole) sources onto an estimated signal subspace and select those with largest correlations. In ERT, secondary sources are excited simultaneously but in different ways, i.e. with distinct amplitude patterns, depending on the locations and amplitudes of primary sources. If the number of receivers is "large enough", different source configurations can lead to a set of observation vectors that span the data subspace. However, since sources that are spatially close to each other have highly correlated signatures, seperation of such signals becomes very difficult in the presence of noise. To overcome this problem we consider iterative MUSIC algorithms like R-MUSIC and RAP-MUSIC. These recursive algorithms pose a computational burden as they require multiple large combinatorial searches. Results obtained with these algorithms using simulated data of different conductivity patterns are presented.
SKRYN: A fast semismooth-Krylov-Newton method for controlling Ising spin systems
NASA Astrophysics Data System (ADS)
Ciaramella, G.; Borzì, A.
2015-05-01
The modeling and control of Ising spin systems is of fundamental importance in NMR spectroscopy applications. In this paper, two computer packages, ReHaG and SKRYN, are presented. Their purpose is to set-up and solve quantum optimal control problems governed by the Liouville master equation modeling Ising spin-1/2 systems with pointwise control constraints. In particular, the MATLAB package ReHaG allows to compute a real matrix representation of the master equation. The MATLAB package SKRYN implements a new strategy resulting in a globalized semismooth matrix-free Krylov-Newton scheme. To discretize the real representation of the Liouville master equation, a norm-preserving modified Crank-Nicolson scheme is used. Results of numerical experiments demonstrate that the SKRYN code is able to provide fast and accurate solutions to the Ising spin quantum optimization problem.
The Krylov accelerated SIMPLE(R) method for flow problems in industrial furnaces
NASA Astrophysics Data System (ADS)
Vuik, C.; Saghir, A.; Boerstoel, G. P.
2000-08-01
Numerical modeling of the melting and combustion process is an important tool in gaining understanding of the physical and chemical phenomena that occur in a gas- or oil-fired glass-melting furnace. The incompressible Navier-Stokes equations are used to model the gas flow in the furnace. The discrete Navier-Stokes equations are solved by the SIMPLE(R) pressure-correction method. In these applications, many SIMPLE(R) iterations are necessary to obtain an accurate solution. In this paper, Krylov accelerated versions are proposed: GCR-SIMPLE(R). The properties of these methods are investigated for a simple two-dimensional flow. Thereafter, the efficiencies of the methods are compared for three-dimensional flows in industrial glass-melting furnaces. Copyright
Software for computing eigenvalue bounds for iterative subspace matrix methods
NASA Astrophysics Data System (ADS)
Shepard, Ron; Minkoff, Michael; Zhou, Yunkai
2005-07-01
This paper describes software for computing eigenvalue bounds to the standard and generalized hermitian eigenvalue problem as described in [Y. Zhou, R. Shepard, M. Minkoff, Computing eigenvalue bounds for iterative subspace matrix methods, Comput. Phys. Comm. 167 (2005) 90-102]. The software discussed in this manuscript applies to any subspace method, including Lanczos, Davidson, SPAM, Generalized Davidson Inverse Iteration, Jacobi-Davidson, and the Generalized Jacobi-Davidson methods, and it is applicable to either outer or inner eigenvalues. This software can be applied during the subspace iterations in order to truncate the iterative process and to avoid unnecessary effort when converging specific eigenvalues to a required target accuracy, and it can be applied to the final set of Ritz values to assess the accuracy of the converged results. Program summaryTitle of program: SUBROUTINE BOUNDS_OPT Catalogue identifier: ADVE Program obtainable from: CPC Program Library, Queen's University of Belfast, N. Ireland Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADVE Computers: any computer that supports a Fortran 90 compiler Operating systems: any computer that supports a Fortran 90 compiler Programming language: Standard Fortran 90 High speed storage required:5m+5 working-precision and 2m+7 integer for m Ritz values No. of bits in a word: The floating point working precision is parameterized with the symbolic constant WP No. of lines in distributed program, including test data, etc.: 2452 No. of bytes in distributed program, including test data, etc.: 281 543 Distribution format: tar.gz Nature of physical problem: The computational solution of eigenvalue problems using iterative subspace methods has widespread applications in the physical sciences and engineering as well as other areas of mathematical modeling (economics, social sciences, etc.). The accuracy of the solution of such problems and the utility of those errors is a fundamental problem that is of
Accurate Excited State Geometries within Reduced Subspace TDDFT/TDA.
Robinson, David
2014-12-01
A method for the calculation of TDDFT/TDA excited state geometries within a reduced subspace of Kohn-Sham orbitals has been implemented and tested. Accurate geometries are found for all of the fluorophore-like molecules tested, with at most all valence occupied orbitals and half of the virtual orbitals included but for some molecules even fewer orbitals. Efficiency gains of between 15 and 30% are found for essentially the same level of accuracy as a standard TDDFT/TDA excited state geometry optimization calculation. PMID:26583218
Is longer sevoflurane preconditioning neuroprotective in permanent focal cerebral ischemia?
Qiu, Caiwei; Sheng, Bo; Wang, Shurong; Liu, Jin
2013-08-15
Sevoflurane preconditioning has neuroprotective effects in the cerebral ischemia/reperfusion model. However, its influence on permanent cerebral ischemia remains unclear. In the present study, the rats were exposed to sevoflurane for 15, 30, 60, and 120 minutes, followed by induction of permanent cerebral ischemia. Results demonstrated that 30- and 60-minute sevoflurane preconditioning significantly reduced the infarct volume at 24 hours after cerebral ischemia, and 60-minute lurane preconditioning additionally reduced the number of TUNEL- and caspase-3-positive cells in the ischemic penumbra. However, 120-minute sevoflurane preconditioning did not show evident neuroprotective effects. Moreover, 60-minute sevoflurane preconditioning significantly attenuated neurological deficits and infarct volume in rats at 4 days after cerebral ischemia. These findings indicated that 60-minute sevoflurane preconditioning can induce the best neuroprotective effects in rats with permanent cerebral ischemia through the inhibition of apoptosis. PMID:25206521
Implicit preconditioned WENO scheme for steady viscous flow computation
NASA Astrophysics Data System (ADS)
Huang, Juan-Chen; Lin, Herng; Yang, Jaw-Yen
2009-02-01
A class of lower-upper symmetric Gauss-Seidel implicit weighted essentially nonoscillatory (WENO) schemes is developed for solving the preconditioned Navier-Stokes equations of primitive variables with Spalart-Allmaras one-equation turbulence model. The numerical flux of the present preconditioned WENO schemes consists of a first-order part and high-order part. For first-order part, we adopt the preconditioned Roe scheme and for the high-order part, we employ preconditioned WENO methods. For comparison purpose, a preconditioned TVD scheme is also given and tested. A time-derivative preconditioning algorithm is devised and a discriminant is devised for adjusting the preconditioning parameters at low Mach numbers and turning off the preconditioning at intermediate or high Mach numbers. The computations are performed for the two-dimensional lid driven cavity flow, low subsonic viscous flow over S809 airfoil, three-dimensional low speed viscous flow over 6:1 prolate spheroid, transonic flow over ONERA-M6 wing and hypersonic flow over HB-2 model. The solutions of the present algorithms are in good agreement with the experimental data. The application of the preconditioned WENO schemes to viscous flows at all speeds not only enhances the accuracy and robustness of resolving shock and discontinuities for supersonic flows, but also improves the accuracy of low Mach number flow with complicated smooth solution structures.
Ischemic preconditioning protects against gap junctional uncoupling in cardiac myofibroblasts.
Sundset, Rune; Cooper, Marie; Mikalsen, Svein-Ole; Ytrehus, Kirsti
2004-01-01
Ischemic preconditioning increases the heart's tolerance to a subsequent longer ischemic period. The purpose of this study was to investigate the role of gap junction communication in simulated preconditioning in cultured neonatal rat cardiac myofibroblasts. Gap junctional intercellular communication was assessed by Lucifer yellow dye transfer. Preconditioning preserved intercellular coupling after prolonged ischemia. An initial reduction in coupling in response to the preconditioning stimulus was also observed. This may protect neighboring cells from damaging substances produced during subsequent regional ischemia in vivo, and may preserve gap junctional communication required for enhanced functional recovery during subsequent reperfusion. PMID:16247851
Preconditioning and the limit to the incompressible flow equations
NASA Technical Reports Server (NTRS)
Turkel, E.; Fiterman, A.; Vanleer, B.
1993-01-01
The use of preconditioning methods to accelerate the convergence to a steady state for both the incompressible and compressible fluid dynamic equations are considered. The relation between them for both the continuous problem and the finite difference approximation is also considered. The analysis relies on the inviscid equations. The preconditioning consists of a matrix multiplying the time derivatives. Hence, the steady state of the preconditioned system is the same as the steady state of the original system. For finite difference methods the preconditioning can change and improve the steady state solutions. An application to flow around an airfoil is presented.
Efficient Calibration of Categorical Parameter Distributions using Subspace Methods
NASA Astrophysics Data System (ADS)
Khambhammettu, P.; Renard, P.; Doherty, J.
2014-12-01
Categorical parameter distributions are common-place in hydrogeological systems consisting of rock-types / aquifer materials with distinct properties, eg: sand channels in a clay matrix. Model calibration is difficult in such systems because the inverse problem is hindered by the discontinuities in the parameter space. In this paper, we present two approaches based on sub-space methods to generate categorical parameter distributions of aquifer parameters that meet calibration constraints (eg:- measured water level data, gradients) while honoring prior geological constraints. In the first approach, the prior geological information and acceptable parameter distributions are encapsulated in a simple object-based model. In the second approach, a Multiple-Point Statistics simulator is used to represent the prior geological information. Sub-space methods in conjunction with dynamic pilot points are then employed to explore the parameter space and determine the parameter combinations that optimally honor geologic and calibration constraints. Using a simple aquifer system, we demonstrate that the new approach is capable of quickly generating multiple multiple parameter distributions that honor both geological and calibration constraints. We also explore the underlying parameter and predictive uncertainty using Null Space Monte Carlo techniques.
LogDet Rank Minimization with Application to Subspace Clustering.
Kang, Zhao; Peng, Chong; Cheng, Jie; Cheng, Qiang
2015-01-01
Low-rank matrix is desired in many machine learning and computer vision problems. Most of the recent studies use the nuclear norm as a convex surrogate of the rank operator. However, all singular values are simply added together by the nuclear norm, and thus the rank may not be well approximated in practical problems. In this paper, we propose using a log-determinant (LogDet) function as a smooth and closer, though nonconvex, approximation to rank for obtaining a low-rank representation in subspace clustering. Augmented Lagrange multipliers strategy is applied to iteratively optimize the LogDet-based nonconvex objective function on potentially large-scale data. By making use of the angular information of principal directions of the resultant low-rank representation, an affinity graph matrix is constructed for spectral clustering. Experimental results on motion segmentation and face clustering data demonstrate that the proposed method often outperforms state-of-the-art subspace clustering algorithms. PMID:26229527
Inverse rendering of Lambertian surfaces using subspace methods.
Nguyen, Ha Q; Do, Minh N
2014-12-01
We propose a vector space approach for inverse rendering of a Lambertian convex object with distant light sources. In this problem, the texture of the object and arbitrary lightings are both to be recovered from multiple images of the object and its 3D model. Our work is motivated by the observation that all possible images of a Lambertian object lie around a low-dimensional linear subspace spanned by the first few spherical harmonics. The inverse rendering can therefore be formulated as a matrix factorization, in which the basis of the subspace is encoded in a spherical harmonic matrix S associated with the object’s geometry. A necessary and sufficient condition on S for unique factorization is derived with an introduction to a new notion of matrix rank called nonseparable full rank. A singular value decomposition-based algorithm for exact factorization in the noiseless case is introduced. In the presence of noise, two algorithms, namely, alternating and optimization based are proposed to deal with two different types of noise. A random sample consensus-based algorithm is introduced to reduce the size of the optimization problem, which is equal to the number of pixels in each image. Implementations of the proposed algorithms are done on a real data set. PMID:25373083
Conformal Laplace superintegrable systems in 2D: polynomial invariant subspaces
NASA Astrophysics Data System (ADS)
Escobar-Ruiz, M. A.; Miller, Willard, Jr.
2016-07-01
2nd-order conformal superintegrable systems in n dimensions are Laplace equations on a manifold with an added scalar potential and 2n-1 independent 2nd order conformal symmetry operators. They encode all the information about Helmholtz (eigenvalue) superintegrable systems in an efficient manner: there is a 1-1 correspondence between Laplace superintegrable systems and Stäckel equivalence classes of Helmholtz superintegrable systems. In this paper we focus on superintegrable systems in two-dimensions, n = 2, where there are 44 Helmholtz systems, corresponding to 12 Laplace systems. For each Laplace equation we determine the possible two-variate polynomial subspaces that are invariant under the action of the Laplace operator, thus leading to families of polynomial eigenfunctions. We also study the behavior of the polynomial invariant subspaces under a Stäckel transform. The principal new results are the details of the polynomial variables and the conditions on parameters of the potential corresponding to polynomial solutions. The hidden gl 3-algebraic structure is exhibited for the exact and quasi-exact systems. For physically meaningful solutions, the orthogonality properties and normalizability of the polynomials are presented as well. Finally, for all Helmholtz superintegrable solvable systems we give a unified construction of one-dimensional (1D) and two-dimensional (2D) quasi-exactly solvable potentials possessing polynomial solutions, and a construction of new 2D PT-symmetric potentials is established.
NASA Astrophysics Data System (ADS)
Zhang, Xing; Wen, Gongjian
2015-10-01
Anomaly detection (AD) becomes increasingly important in hyperspectral imagery analysis with many practical applications. Local orthogonal subspace projection (LOSP) detector is a popular anomaly detector which exploits local endmembers/eigenvectors around the pixel under test (PUT) to construct background subspace. However, this subspace only takes advantage of the spectral information, but the spatial correlat ion of the background clutter is neglected, which leads to the anomaly detection result sensitive to the accuracy of the estimated subspace. In this paper, a local three dimensional orthogonal subspace projection (3D-LOSP) algorithm is proposed. Firstly, under the jointly use of both spectral and spatial information, three directional background subspaces are created along the image height direction, the image width direction and the spectral direction, respectively. Then, the three corresponding orthogonal subspaces are calculated. After that, each vector along three direction of the local cube is projected onto the corresponding orthogonal subspace. Finally, a composite score is given through the three direction operators. In 3D-LOSP, the anomalies are redefined as the target not only spectrally different to the background, but also spatially distinct. Thanks to the addition of the spatial information, the robustness of the anomaly detection result has been improved greatly by the proposed 3D-LOSP algorithm. It is noteworthy that the proposed algorithm is an expansion of LOSP and this ideology can inspire many other spectral-based anomaly detection methods. Experiments with real hyperspectral images have proved the stability of the detection result.
ERIC Educational Resources Information Center
Wawro, Megan; Sweeney, George F.; Rabin, Jeffrey M.
2011-01-01
This paper reports on a study investigating students' ways of conceptualizing key ideas in linear algebra, with the particular results presented here focusing on student interactions with the notion of subspace. In interviews conducted with eight undergraduates, we found students' initial descriptions of subspace often varied substantially from…
Parallel preconditioning techniques for sparse CG solvers
Basermann, A.; Reichel, B.; Schelthoff, C.
1996-12-31
Conjugate gradient (CG) methods to solve sparse systems of linear equations play an important role in numerical methods for solving discretized partial differential equations. The large size and the condition of many technical or physical applications in this area result in the need for efficient parallelization and preconditioning techniques of the CG method. In particular for very ill-conditioned matrices, sophisticated preconditioner are necessary to obtain both acceptable convergence and accuracy of CG. Here, we investigate variants of polynomial and incomplete Cholesky preconditioners that markedly reduce the iterations of the simply diagonally scaled CG and are shown to be well suited for massively parallel machines.
Domain-decomposed preconditionings for transport operators
NASA Technical Reports Server (NTRS)
Chan, Tony F.; Gropp, William D.; Keyes, David E.
1991-01-01
The performance was tested of five different interface preconditionings for domain decomposed convection diffusion problems, including a novel one known as the spectral probe, while varying mesh parameters, Reynolds number, ratio of subdomain diffusion coefficients, and domain aspect ratio. The preconditioners are representative of the range of practically computable possibilities that have appeared in the domain decomposition literature for the treatment of nonoverlapping subdomains. It is shown that through a large number of numerical examples that no single preconditioner can be considered uniformly superior or uniformly inferior to the rest, but that knowledge of particulars, including the shape and strength of the convection, is important in selecting among them in a given problem.
Extremely Intense Magnetospheric Substorms : External Triggering? Preconditioning?
NASA Astrophysics Data System (ADS)
Tsurutani, Bruce; Echer, Ezequiel; Hajra, Rajkumar
2016-07-01
We study particularly intense substorms using a variety of near-Earth spacecraft data and ground observations. We will relate the solar cycle dependences of events, determine whether the supersubstorms are externally or internally triggered, and their relationship to other factors such as magnetospheric preconditioning. If time permits, we will explore the details of the events and whether they are similar to regular (Akasofu, 1964) substorms or not. These intense substorms are an important feature of space weather since they may be responsible for power outages.
H(curl) Auxiliary Mesh Preconditioning
Kolev, T V; Pasciak, J E; Vassilevski, P S
2006-08-31
This paper analyzes a two-level preconditioning scheme for H(curl) bilinear forms. The scheme utilizes an auxiliary problem on a related mesh that is more amenable for constructing optimal order multigrid methods. More specifically, we analyze the case when the auxiliary mesh only approximately covers the original domain. The latter assumption is important since it allows for easy construction of nested multilevel spaces on regular auxiliary meshes. Numerical experiments in both two and three space dimensions illustrate the optimal performance of the method.
Towards bulk based preconditioning for quantum dotcomputations
Dongarra, Jack; Langou, Julien; Tomov, Stanimire; Channing,Andrew; Marques, Osni; Vomel, Christof; Wang, Lin-Wang
2006-05-25
This article describes how to accelerate the convergence of Preconditioned Conjugate Gradient (PCG) type eigensolvers for the computation of several states around the band gap of colloidal quantum dots. Our new approach uses the Hamiltonian from the bulk materials constituent for the quantum dot to design an efficient preconditioner for the folded spectrum PCG method. The technique described shows promising results when applied to CdSe quantum dot model problems. We show a decrease in the number of iteration steps by at least a factor of 4 compared to the previously used diagonal preconditioner.
Parallel Preconditioning for CFD Problems on the CM-5
NASA Technical Reports Server (NTRS)
Simon, Horst D.; Kremenetsky, Mark D.; Richardson, John; Lasinski, T. A. (Technical Monitor)
1994-01-01
Up to today, preconditioning methods on massively parallel systems have faced a major difficulty. The most successful preconditioning methods in terms of accelerating the convergence of the iterative solver such as incomplete LU factorizations are notoriously difficult to implement on parallel machines for two reasons: (1) the actual computation of the preconditioner is not very floating-point intensive, but requires a large amount of unstructured communication, and (2) the application of the preconditioning matrix in the iteration phase (i.e. triangular solves) are difficult to parallelize because of the recursive nature of the computation. Here we present a new approach to preconditioning for very large, sparse, unsymmetric, linear systems, which avoids both difficulties. We explicitly compute an approximate inverse to our original matrix. This new preconditioning matrix can be applied most efficiently for iterative methods on massively parallel machines, since the preconditioning phase involves only a matrix-vector multiplication, with possibly a dense matrix. Furthermore the actual computation of the preconditioning matrix has natural parallelism. For a problem of size n, the preconditioning matrix can be computed by solving n independent small least squares problems. The algorithm and its implementation on the Connection Machine CM-5 are discussed in detail and supported by extensive timings obtained from real problem data.
[STRESS AND INFARCT LIMITING EFFECTS OF EARLY HYPOXIC PRECONDITIONING].
Lishmanov, Yu B; Maslov, L N; Sementsov, A S; Naryzhnaya, N V; Tsibulnikov, S Yu
2015-09-01
It was established that early hypoxic preconditioning is an adaptive state different from eustress and distress. Hypoxic preconditioning has the cross effects, increasing the tolerance of the heart to ischemia-reperfusion and providing antiulcerogenic effect during immobilization stress. PMID:26672158
40 CFR 86.132-00 - Vehicle preconditioning.
Code of Federal Regulations, 2010 CFR
2010-07-01
... tested for the SFTP supplemental tests of aggressive driving (US06) and air conditioning (SC03). Section...) Air Conditioning Test (SC03) Preconditioning. (1) If the SC03 test follows the exhaust emission FTP or... preconditioning cycles for the SC03 air conditioning test and the 10 minute soak are conducted at the same...
40 CFR 1066.407 - Vehicle preparation and preconditioning.
Code of Federal Regulations, 2012 CFR
2012-07-01
...) Prepare the vehicle for testing as described in 40 CFR 86.131. (b) If testing will include measurement of refueling emissions, perform the vehicle preconditioning steps as described in 40 CFR 86.153. Otherwise, perform the vehicle preconditioning steps as described in 40 CFR 86.132....
40 CFR 1066.407 - Vehicle preparation and preconditioning.
Code of Federal Regulations, 2013 CFR
2013-07-01
...) Prepare the vehicle for testing as described in 40 CFR 86.131. (b) If testing will include measurement of refueling emissions, perform the vehicle preconditioning steps as described in 40 CFR 86.153. Otherwise, perform the vehicle preconditioning steps as described in 40 CFR 86.132....
40 CFR 86.532-78 - Vehicle preconditioning.
Code of Federal Regulations, 2011 CFR
2011-07-01
... 40 Protection of Environment 18 2011-07-01 2011-07-01 false Vehicle preconditioning. 86.532-78... (CONTINUED) CONTROL OF EMISSIONS FROM NEW AND IN-USE HIGHWAY VEHICLES AND ENGINES Emission Regulations for 1978 and Later New Motorcycles; Test Procedures § 86.532-78 Vehicle preconditioning. (a) The...
40 CFR 86.532-78 - Vehicle preconditioning.
Code of Federal Regulations, 2013 CFR
2013-07-01
... 40 Protection of Environment 19 2013-07-01 2013-07-01 false Vehicle preconditioning. 86.532-78... (CONTINUED) CONTROL OF EMISSIONS FROM NEW AND IN-USE HIGHWAY VEHICLES AND ENGINES Emission Regulations for 1978 and Later New Motorcycles; Test Procedures § 86.532-78 Vehicle preconditioning. (a) The...
40 CFR 86.532-78 - Vehicle preconditioning.
Code of Federal Regulations, 2010 CFR
2010-07-01
... 40 Protection of Environment 18 2010-07-01 2010-07-01 false Vehicle preconditioning. 86.532-78... (CONTINUED) CONTROL OF EMISSIONS FROM NEW AND IN-USE HIGHWAY VEHICLES AND ENGINES Emission Regulations for 1978 and Later New Motorcycles; Test Procedures § 86.532-78 Vehicle preconditioning. (a) The...
Reduced-order preconditioning for bidomain simulations.
Deo, Makarand; Bauer, Steffen; Plank, Gernot; Vigmond, Edward
2007-05-01
Simulations of the bidomain equations involve solving large, sparse, linear systems of the form Ax = b. Being an initial value problems, it is solved at every time step. Therefore, efficient solvers are essential to keep simulations tractable. Iterative solvers, especially the preconditioned conjugate gradient (PCG) method, are attractive since memory demands are minimized compared to direct methods, albeit at the cost of solution speed. However, a proper preconditioner can drastically speed up the solution process by reducing the number of iterations. In this paper, a novel preconditioner for the PCG method based on system order reduction using the Arnoldi method (A-PCG) is proposed. Large order systems, generated during cardiac bidomain simulations employing a finite element method formulation, are solved with the A-PCG method. Its performance is compared with incomplete LU (ILU) preconditioning. Results indicate that the A-PCG estimates an approximate solution considerably faster than the ILU, often within a single iteration. To reduce the computational demands in terms of memory and run time, the use of a cascaded preconditioner was suggested. The A-PCG was applied to quickly obtain an approximate solution, and subsequently a cheap iterative method such as successive overrelaxation (SOR) is applied to further refine the solution to arrive at a desired accuracy. The memory requirements are less than those of direct LU but more than ILU method. The proposed scheme is shown to yield significant speedups when solving time evolving systems. PMID:17518292
The multigrid preconditioned conjugate gradient method
NASA Technical Reports Server (NTRS)
Tatebe, Osamu
1993-01-01
A multigrid preconditioned conjugate gradient method (MGCG method), which uses the multigrid method as a preconditioner of the PCG method, is proposed. The multigrid method has inherent high parallelism and improves convergence of long wavelength components, which is important in iterative methods. By using this method as a preconditioner of the PCG method, an efficient method with high parallelism and fast convergence is obtained. First, it is considered a necessary condition of the multigrid preconditioner in order to satisfy requirements of a preconditioner of the PCG method. Next numerical experiments show a behavior of the MGCG method and that the MGCG method is superior to both the ICCG method and the multigrid method in point of fast convergence and high parallelism. This fast convergence is understood in terms of the eigenvalue analysis of the preconditioned matrix. From this observation of the multigrid preconditioner, it is realized that the MGCG method converges in very few iterations and the multigrid preconditioner is a desirable preconditioner of the conjugate gradient method.
Universal quantum computation in waveguide QED using decoherence free subspaces
NASA Astrophysics Data System (ADS)
Paulisch, V.; Kimble, H. J.; González-Tudela, A.
2016-04-01
The interaction of quantum emitters with one-dimensional photon-like reservoirs induces strong and long-range dissipative couplings that give rise to the emergence of the so-called decoherence free subspaces (DFSs) which are decoupled from dissipation. When introducing weak perturbations on the emitters, e.g., driving, the strong collective dissipation enforces an effective coherent evolution within the DFS. In this work, we show explicitly how by introducing single-site resolved drivings, we can use the effective dynamics within the DFS to design a universal set of one and two-qubit gates within the DFS of an ensemble of two-level atom-like systems. Using Liouvillian perturbation theory we calculate the scaling with the relevant figures of merit of the systems, such as the Purcell factor and imperfect control of the drivings. Finally, we compare our results with previous proposals using atomic Λ systems in leaky cavities.
Cross-Modal Subspace Learning via Pairwise Constraints.
He, Ran; Zhang, Man; Wang, Liang; Ji, Ye; Yin, Qiyue
2015-12-01
In multimedia applications, the text and image components in a web document form a pairwise constraint that potentially indicates the same semantic concept. This paper studies cross-modal learning via the pairwise constraint and aims to find the common structure hidden in different modalities. We first propose a compound regularization framework to address the pairwise constraint, which can be used as a general platform for developing cross-modal algorithms. For unsupervised learning, we propose a multi-modal subspace clustering method to learn a common structure for different modalities. For supervised learning, to reduce the semantic gap and the outliers in pairwise constraints, we propose a cross-modal matching method based on compound ℓ21 regularization. Extensive experiments demonstrate the benefits of joint text and image modeling with semantically induced pairwise constraints, and they show that the proposed cross-modal methods can further reduce the semantic gap between different modalities and improve the clustering/matching accuracy. PMID:26259218
Parallel iterative methods for sparse linear and nonlinear equations
NASA Technical Reports Server (NTRS)
Saad, Youcef
1989-01-01
As three-dimensional models are gaining importance, iterative methods will become almost mandatory. Among these, preconditioned Krylov subspace methods have been viewed as the most efficient and reliable, when solving linear as well as nonlinear systems of equations. There has been several different approaches taken to adapt iterative methods for supercomputers. Some of these approaches are discussed and the methods that deal more specifically with general unstructured sparse matrices, such as those arising from finite element methods, are emphasized.
A nested iterative scheme for computation of incompressible flows in long domains
NASA Astrophysics Data System (ADS)
Manguoglu, Murat; Sameh, Ahmed H.; Tezduyar, Tayfun E.; Sathe, Sunil
2008-12-01
We present an effective preconditioning technique for solving the nonsymmetric linear systems encountered in computation of incompressible flows in long domains. The application category we focus on is arterial fluid mechanics. These linear systems are solved using a nested iterative scheme with an outer Richardson scheme and an inner iteration that is handled via a Krylov subspace method. Test computations that demonstrate the robustness of our nested scheme are presented.
Recovery Discontinuous Galerkin Jacobian-free Newton-Krylov Method for all-speed flows
HyeongKae Park; Robert Nourgaliev; Vincent Mousseau; Dana Knoll
2008-07-01
There is an increasing interest to develop the next generation simulation tools for the advanced nuclear energy systems. These tools will utilize the state-of-art numerical algorithms and computer science technology in order to maximize the predictive capability, support advanced reactor designs, reduce uncertainty and increase safety margins. In analyzing nuclear energy systems, we are interested in compressible low-Mach number, high heat flux flows with a wide range of Re, Ra, and Pr numbers. Under these conditions, the focus is placed on turbulent heat transfer, in contrast to other industries whose main interest is in capturing turbulent mixing. Our objective is to develop singlepoint turbulence closure models for large-scale engineering CFD code, using Direct Numerical Simulation (DNS) or Large Eddy Simulation (LES) tools, requireing very accurate and efficient numerical algorithms. The focus of this work is placed on fully-implicit, high-order spatiotemporal discretization based on the discontinuous Galerkin method solving the conservative form of the compressible Navier-Stokes equations. The method utilizes a local reconstruction procedure derived from weak formulation of the problem, which is inspired by the recovery diffusion flux algorithm of van Leer and Nomura [?] and by the piecewise parabolic reconstruction [?] in the finite volume method. The developed methodology is integrated into the Jacobianfree Newton-Krylov framework [?] to allow a fully-implicit solution of the problem.
A fast, preconditioned conjugate gradient Toeplitz solver
NASA Technical Reports Server (NTRS)
Pan, Victor; Schrieber, Robert
1989-01-01
A simple factorization is given of an arbitrary hermitian, positive definite matrix in which the factors are well-conditioned, hermitian, and positive definite. In fact, given knowledge of the extreme eigenvalues of the original matrix A, an optimal improvement can be achieved, making the condition numbers of each of the two factors equal to the square root of the condition number of A. This technique is to applied to the solution of hermitian, positive definite Toeplitz systems. Large linear systems with hermitian, positive definite Toeplitz matrices arise in some signal processing applications. A stable fast algorithm is given for solving these systems that is based on the preconditioned conjugate gradient method. The algorithm exploits Toeplitz structure to reduce the cost of an iteration to O(n log n) by applying the fast Fourier Transform to compute matrix-vector products. Matrix factorization is used as a preconditioner.
Iterative image restoration using approximate inverse preconditioning.
Nagy, J G; Plemmons, R J; Torgersen, T C
1996-01-01
Removing a linear shift-invariant blur from a signal or image can be accomplished by inverse or Wiener filtering, or by an iterative least-squares deblurring procedure. Because of the ill-posed characteristics of the deconvolution problem, in the presence of noise, filtering methods often yield poor results. On the other hand, iterative methods often suffer from slow convergence at high spatial frequencies. This paper concerns solving deconvolution problems for atmospherically blurred images by the preconditioned conjugate gradient algorithm, where a new approximate inverse preconditioner is used to increase the rate of convergence. Theoretical results are established to show that fast convergence can be expected, and test results are reported for a ground-based astronomical imaging problem. PMID:18285203
Mitochondria: the missing link between preconditioning and neuroprotection.
Correia, Sónia C; Santos, Renato X; Perry, George; Zhu, Xiongwei; Moreira, Paula I; Smith, Mark A
2010-01-01
The quote "what does not kill you makes you stronger" perfectly describes the preconditioning phenomenon - a paradigm that affords robust brain tolerance in the face of neurodegenerative insults. Over the last few decades, many attempts have been made to identify the molecular mechanisms involved in preconditioning-induced protective responses, and recent data suggests that many of these mechanisms converge on the mitochondria, positing mitochondria as master regulators of preconditioning-triggered endogenous neuroprotection. In this review, we critically discuss evidence for the involvement of mitochondria within the preconditioning paradigm. We will highlight the crucial targets and mediators by which mitochondria are integrated into neuroprotective signaling pathways that underlie preconditioning, putting focus on mitochondrial respiratory chain and mitochondrial reactive oxygen species, mitochondrial ATP-sensitive potassium channels, mitochondrial permeability transition pore, uncoupling proteins, and mitochondrial antioxidant enzyme manganese superoxide dismutase. We also discuss the role of mitochondria in the induction of hypoxia-inducible factor-1, a transcription factor engaged in preconditioning-mediated neuroprotective effects. The identification of intrinsic mitochondrial mechanisms involved in preconditioning will provide new insights which can be translated into potential pharmacological interventions aimed at counteracting neurodegeneration. PMID:20463394
Hyperbaric oxygen preconditioning protects rats against CNS oxygen toxicity.
Arieli, Yehuda; Kotler, Doron; Eynan, Mirit; Hochman, Ayala
2014-06-15
We examined the hypothesis that repeated exposure to non-convulsive hyperbaric oxygen (HBO) as preconditioning provides protection against central nervous system oxygen toxicity (CNS-OT). Four groups of rats were used in the study. Rats in the control and the negative control (Ctl-) groups were kept in normobaric air. Two groups of rats were preconditioned to non-convulsive HBO at 202 kPa for 1h once every other day for a total of three sessions. Twenty-four hours after preconditioning, one of the preconditioned groups and the control rats were exposed to convulsive HBO at 608 kPa, and latency to CNS-OT was measured. Ctl- rats and the second preconditioned group (PrC-) were not subjected to convulsive HBO exposure. Tissues harvested from the hippocampus and frontal cortex were evaluated for enzymatic activity and nitrotyrosine levels. In the group exposed to convulsive oxygen at 608 kPa, latency to CNS-OT increased from 12.8 to 22.4 min following preconditioning. A significant decrease in the activity of glutathione reductase and glucose-6-phosphate dehydrogenase, and a significant increase in glutathione peroxidase activity, was observed in the hippocampus of preconditioned rats. Nitrotyrosine levels were significantly lower in the preconditioned animals, the highest level being observed in the control rats. In the cortex of the preconditioned rats, a significant increase was observed in glutathione S-transferase and glutathione peroxidase activity. Repeated exposure to non-convulsive HBO provides protection against CNS-OT. The protective mechanism involves alterations in the enzymatic activity of the antioxidant system and lower levels of peroxynitrite, mainly in the hippocampus. PMID:24675062
Visual Exploration of High-Dimensional Data through Subspace Analysis and Dynamic Projections
Liu, S.; Wang, B.; Thiagarajan, Jayaraman J.; Bremer, Peer -Timo; Pascucci, Valerio
2015-06-01
We introduce a novel interactive framework for visualizing and exploring high-dimensional datasets based on subspace analysis and dynamic projections. We assume the high-dimensional dataset can be represented by a mixture of low-dimensional linear subspaces with mixed dimensions, and provide a method to reliably estimate the intrinsic dimension and linear basis of each subspace extracted from the subspace clustering. Subsequently, we use these bases to define unique 2D linear projections as viewpoints from which to visualize the data. To understand the relationships among the different projections and to discover hidden patterns, we connect these projections through dynamic projections that create smooth animated transitions between pairs of projections. We introduce the view transition graph, which provides flexible navigation among these projections to facilitate an intuitive exploration. Finally, we provide detailed comparisons with related systems, and use real-world examples to demonstrate the novelty and usability of our proposed framework.
Building Ultra-Low False Alarm Rate Support Vector Classifier Ensembles Using Random Subspaces
Chen, B Y; Lemmond, T D; Hanley, W G
2008-10-06
This paper presents the Cost-Sensitive Random Subspace Support Vector Classifier (CS-RS-SVC), a new learning algorithm that combines random subspace sampling and bagging with Cost-Sensitive Support Vector Classifiers to more effectively address detection applications burdened by unequal misclassification requirements. When compared to its conventional, non-cost-sensitive counterpart on a two-class signal detection application, random subspace sampling is shown to very effectively leverage the additional flexibility offered by the Cost-Sensitive Support Vector Classifier, yielding a more than four-fold increase in the detection rate at a false alarm rate (FAR) of zero. Moreover, the CS-RS-SVC is shown to be fairly robust to constraints on the feature subspace dimensionality, enabling reductions in computation time of up to 82% with minimal performance degradation.
Subspace-based CFAR detection of vehicles from forests in SAR image
NASA Astrophysics Data System (ADS)
Zhang, Yanfei; Guan, Jian; Wang, Jie; Li, Hongwei
2005-11-01
Automatic detection of military vehicles hidden among forests in synthetic aperture radar (SAR) image is a challenging and difficult task because tree trunk clutter often appears as locally bright as obscured targets. We apply subspace-based detection methods to treat the problem as detecting subspace signals in structured subspace interference and broadband noise of unknown level. Specifically, tree trunk clutter is modeled as structured isotropic interferences with unknown amplitudes while dominant vehicle scatterers as anisotropic dihedral responses. Matched subspace detector (MSD) with constant false alarm rate (CFAR) property is derived. Experiments on both simulated and real foliage-penetrating (FOPEN) SAR image show that the proposed detection scheme has good detection performance even at low false alarm rates.
Modulated Hebb-Oja learning rule--a method for principal subspace analysis.
Jankovic, Marko V; Ogawa, Hidemitsu
2006-03-01
This paper presents analysis of the recently proposed modulated Hebb-Oja (MHO) method that performs linear mapping to a lower-dimensional subspace. Principal component subspace is the method that will be analyzed. Comparing to some other well-known methods for yielding principal component subspace (e.g., Oja's Subspace Learning Algorithm), the proposed method has one feature that could be seen as desirable from the biological point of view--synaptic efficacy learning rule does not need the explicit information about the value of the other efficacies to make individual efficacy modification. Also, the simplicity of the "neural circuits" that perform global computations and a fact that their number does not depend on the number of input and output neurons, could be seen as good features of the proposed method. PMID:16566463
Universal quantum computation in decoherence-free subspaces with hot trapped ions
Aolita, Leandro; Davidovich, Luiz; Kim, Kihwan; Haeffner, Hartmut
2007-05-15
We consider interactions that generate a universal set of quantum gates on logical qubits encoded in a collective-dephasing-free subspace, and discuss their implementations with trapped ions. This allows for the removal of the by-far largest source of decoherence in current trapped-ion experiments, collective dephasing. In addition, an explicit parametrization of all two-body Hamiltonians able to generate such gates without the system's state ever exiting the protected subspace is provided.
Quantum Recurrence of a Subspace and Operator-Valued Schur Functions
NASA Astrophysics Data System (ADS)
Bourgain, J.; Grünbaum, F. A.; Velázquez, L.; Wilkening, J.
2014-08-01
A notion of monitored recurrence for discrete-time quantum processes was recently introduced in Grünbaum et al. (Commun Math Phys (2), 320:543-569,
Efficient variational Bayesian approximation method based on subspace optimization.
Zheng, Yuling; Fraysse, Aurélia; Rodet, Thomas
2015-02-01
Variational Bayesian approximations have been widely used in fully Bayesian inference for approximating an intractable posterior distribution by a separable one. Nevertheless, the classical variational Bayesian approximation (VBA) method suffers from slow convergence to the approximate solution when tackling large dimensional problems. To address this problem, we propose in this paper a more efficient VBA method. Actually, variational Bayesian issue can be seen as a functional optimization problem. The proposed method is based on the adaptation of subspace optimization methods in Hilbert spaces to the involved function space, in order to solve this optimization problem in an iterative way. The aim is to determine an optimal direction at each iteration in order to get a more efficient method. We highlight the efficiency of our new VBA method and demonstrate its application to image processing by considering an ill-posed linear inverse problem using a total variation prior. Comparisons with state of the art variational Bayesian methods through a numerical example show a notable improvement in computation time. PMID:25532179
Linear parameter varying battery model identification using subspace methods
NASA Astrophysics Data System (ADS)
Hu, Y.; Yurkovich, S.
2011-03-01
The advent of hybrid and plug-in hybrid electric vehicles has created a demand for more precise battery pack management systems (BMS). Among methods used to design various components of a BMS, such as state-of-charge (SoC) estimators, model based approaches offer a good balance between accuracy, calibration effort and implementability. Because models used for these approaches are typically low in order and complexity, the traditional approach is to identify linear (or slightly nonlinear) models that are scheduled based on operating conditions. These models, formally known as linear parameter varying (LPV) models, tend to be difficult to identify because they contain a large amount of coefficients that require calibration. Consequently, the model identification process can be very laborious and time-intensive. This paper describes a comprehensive identification algorithm that uses linear-algebra-based subspace methods to identify a parameter varying state variable model that can describe the input-to-output dynamics of a battery under various operating conditions. Compared with previous methods, this approach is much faster and provides the user with information on the order of the system without placing an a priori structure on the system matrices. The entire process and various nuances are demonstrated using data collected from a lithium ion battery, and the focus is on applications for energy storage in automotive applications.
Robust Semi-Supervised Subspace Clustering via Non-Negative Low-Rank Representation.
Fang, Xiaozhao; Xu, Yong; Li, Xuelong; Lai, Zhihui; Wong, Wai Keung
2016-08-01
Low-rank representation (LRR) has been successfully applied in exploring the subspace structures of data. However, in previous LRR-based semi-supervised subspace clustering methods, the label information is not used to guide the affinity matrix construction so that the affinity matrix cannot deliver strong discriminant information. Moreover, these methods cannot guarantee an overall optimum since the affinity matrix construction and subspace clustering are often independent steps. In this paper, we propose a robust semi-supervised subspace clustering method based on non-negative LRR (NNLRR) to address these problems. By combining the LRR framework and the Gaussian fields and harmonic functions method in a single optimization problem, the supervision information is explicitly incorporated to guide the affinity matrix construction and the affinity matrix construction and subspace clustering are accomplished in one step to guarantee the overall optimum. The affinity matrix is obtained by seeking a non-negative low-rank matrix that represents each sample as a linear combination of others. We also explicitly impose the sparse constraint on the affinity matrix such that the affinity matrix obtained by NNLRR is non-negative low-rank and sparse. We introduce an efficient linearized alternating direction method with adaptive penalty to solve the corresponding optimization problem. Extensive experimental results demonstrate that NNLRR is effective in semi-supervised subspace clustering and robust to different types of noise than other state-of-the-art methods. PMID:26259210
Subspace Leakage Analysis and Improved DOA Estimation With Small Sample Size
NASA Astrophysics Data System (ADS)
Shaghaghi, Mahdi; Vorobyov, Sergiy A.
2015-06-01
Classical methods of DOA estimation such as the MUSIC algorithm are based on estimating the signal and noise subspaces from the sample covariance matrix. For a small number of samples, such methods are exposed to performance breakdown, as the sample covariance matrix can largely deviate from the true covariance matrix. In this paper, the problem of DOA estimation performance breakdown is investigated. We consider the structure of the sample covariance matrix and the dynamics of the root-MUSIC algorithm. The performance breakdown in the threshold region is associated with the subspace leakage where some portion of the true signal subspace resides in the estimated noise subspace. In this paper, the subspace leakage is theoretically derived. We also propose a two-step method which improves the performance by modifying the sample covariance matrix such that the amount of the subspace leakage is reduced. Furthermore, we introduce a phenomenon named as root-swap which occurs in the root-MUSIC algorithm in the low sample size region and degrades the performance of the DOA estimation. A new method is then proposed to alleviate this problem. Numerical examples and simulation results are given for uncorrelated and correlated sources to illustrate the improvement achieved by the proposed methods. Moreover, the proposed algorithms are combined with the pseudo-noise resampling method to further improve the performance.
NASA Astrophysics Data System (ADS)
Sekihara, Kensuke; Kawabata, Yuya; Ushio, Shuta; Sumiya, Satoshi; Kawabata, Shigenori; Adachi, Yoshiaki; Nagarajan, Srikantan S.
2016-06-01
Objective. In functional electrophysiological imaging, signals are often contaminated by interference that can be of considerable magnitude compared to the signals of interest. This paper proposes a novel algorithm for removing such interferences that does not require separate noise measurements. Approach. The algorithm is based on a dual definition of the signal subspace in the spatial- and time-domains. Since the algorithm makes use of this duality, it is named the dual signal subspace projection (DSSP). The DSSP algorithm first projects the columns of the measured data matrix onto the inside and outside of the spatial-domain signal subspace, creating a set of two preprocessed data matrices. The intersection of the row spans of these two matrices is estimated as the time-domain interference subspace. The original data matrix is projected onto the subspace that is orthogonal to this interference subspace. Main results. The DSSP algorithm is validated by using the computer simulation, and using two sets of real biomagnetic data: spinal cord evoked field data measured from a healthy volunteer and magnetoencephalography data from a patient with a vagus nerve stimulator. Significance. The proposed DSSP algorithm is effective for removing overlapped interference in a wide variety of biomagnetic measurements.
Preconditioning methods for improved convergence rates in iterative reconstructions
Clinthorne, N.H.; Chiao, Pingchun; Rogers, W.L. . Div. of Nuclear Medicine); Pan, T.S. . Dept. of Nuclear Medicine); Stamos, J.A. . Dept. of Nuclear Engineering)
1993-03-01
Because of the characteristics of the tomographic inversion problem, iterative reconstruction techniques often suffer from poor convergence rates--especially at high spatial frequencies. By using preconditioning methods, the convergence properties of most iterative methods can be greatly enhanced without changing their ultimate solution. To increase reconstruction speed, the authors have applied spatially-invariant preconditioning filters that can be designed using the tomographic system response and implemented using 2-D frequency-domain filtering techniques. In a sample application, the authors performed reconstructions from noiseless, simulated projection data, using preconditioned and conventional steepest-descent algorithms. The preconditioned methods demonstrated residuals that were up to a factor of 30 lower than the unassisted algorithms at the same iteration. Applications of these methods to regularized reconstructions from projection data containing Poisson noise showed similar, although not as dramatic, behavior.
The Galvanotactic Migration of Keratinocytes is Enhanced by Hypoxic Preconditioning
Guo, Xiaowei; Jiang, Xupin; Ren, Xi; Sun, Huanbo; Zhang, Dongxia; Zhang, Qiong; Zhang, Jiaping; Huang, Yuesheng
2015-01-01
The endogenous electric field (EF)-directed migration of keratinocytes (galvanotaxis) into wounds is an essential step in wound re-epithelialization. Hypoxia, which occurs immediately after injury, acts as an early stimulus to initiate the healing process; however, the mechanisms for this effect, remain elusive. We show here that the galvanotactic migration of keratinocytes was enhanced by hypoxia preconditioning as a result of the increased directionality rather than the increased motility of keratinocytes. This enhancement was both oxygen tension- and preconditioning time-dependent, with the maximum effects achieved using 2% O2 preconditioning for 6 hours. Hypoxic preconditioning (2% O2, 6 hours) decreased the threshold voltage of galvanotaxis to < 25 mV/mm, whereas this value was between 25 and 50 mV/mm in the normal culture control. In a scratch-wound monolayer assay in which the applied EF was in the default healing direction, hypoxic preconditioning accelerated healing by 1.38-fold compared with the control conditions. Scavenging of the induced ROS by N-acetylcysteine (NAC) abolished the enhanced galvanotaxis and the accelerated healing by hypoxic preconditioning. Our data demonstrate a novel and unsuspected role of hypoxia in supporting keratinocyte galvanotaxis. Enhancing the galvanotactic response of cells might therefore be a clinically attractive approach to induce improved wound healing. PMID:25988491
A Weakest Precondition Approach to Robustness
NASA Astrophysics Data System (ADS)
Balliu, Musard; Mastroeni, Isabella
With the increasing complexity of information management computer systems, security becomes a real concern. E-government, web-based financial transactions or military and health care information systems are only a few examples where large amount of information can reside on different hosts distributed worldwide. It is clear that any disclosure or corruption of confidential information in these contexts can result fatal. Information flow controls constitute an appealing and promising technology to protect both data confidentiality and data integrity. The certification of the security degree of a program that runs in untrusted environments still remains an open problem in the area of language-based security. Robustness asserts that an active attacker, who can modify program code in some fixed points (holes), is unable to disclose more private information than a passive attacker, who merely observes unclassified data. In this paper, we extend a method recently proposed for checking declassified non-interference in presence of passive attackers only, in order to check robustness by means of weakest precondition semantics. In particular, this semantics simulates the kind of analysis that can be performed by an attacker, i.e., from public output towards private input. The choice of semantics allows us to distinguish between different attacks models and to characterize the security of applications in different scenarios.
Responsive corneosurfametry following in vivo skin preconditioning.
Uhoda, E; Goffin, V; Pierard, G E
2003-12-01
Skin is subjected to many environmental threats, some of which altering the structure and function of the stratum corneum. Among them, surfactants are recognized factors that may influence irritant contact dermatitis. The present study was conducted to compare the variations in skin capacitance and corneosurfametry (CSM) reactivity before and after skin exposure to repeated subclinical injuries by 2 hand dishwashing liquids. A forearm immersion test was performed on 30 healthy volunteers. 2 daily soak sessions were performed for 5 days. At inclusion and the day following the last soak session, skin capacitance was measured and cyanoacrylate skin-surface strippings were harvested. The latter specimens were used for the ex vivo microwave CSM. Both types of assessments clearly differentiated the 2 hand dishwashing liquids. The forearm immersion test allowed the discriminant sensitivity of CSM to increase. Intact skin capacitance did not predict CSM data. By contrast, a significant correlation was found between the post-test conductance and the corresponding CSM data. In conclusion, a forearm immersion test under realistic conditions can discriminate the irritation potential between surfactant-based products by measuring skin conductance and performing CSM. In vivo skin preconditioning by surfactants increases CSM sensitivity to the same surfactants. PMID:15025702
Discrete sensitivity derivatives of the Navier-Stokes equations with a parallel Krylov solver
NASA Technical Reports Server (NTRS)
Ajmani, Kumud; Taylor, Arthur C., III
1994-01-01
This paper solves an 'incremental' form of the sensitivity equations derived by differentiating the discretized thin-layer Navier Stokes equations with respect to certain design variables of interest. The equations are solved with a parallel, preconditioned Generalized Minimal RESidual (GMRES) solver on a distributed-memory architecture. The 'serial' sensitivity analysis code is parallelized by using the Single Program Multiple Data (SPMD) programming model, domain decomposition techniques, and message-passing tools. Sensitivity derivatives are computed for low and high Reynolds number flows over a NACA 1406 airfoil on a 32-processor Intel Hypercube, and found to be identical to those computed on a single-processor Cray Y-MP. It is estimated that the parallel sensitivity analysis code has to be run on 40-50 processors of the Intel Hypercube in order to match the single-processor processing time of a Cray Y-MP.
Evaluating the utility of mid-infrared spectral subspaces for predicting soil properties
Sila, Andrew M.; Shepherd, Keith D.; Pokhariyal, Ganesh P.
2016-01-01
We propose four methods for finding local subspaces in large spectral libraries. The proposed four methods include (a) cosine angle spectral matching; (b) hit quality index spectral matching; (c) self-organizing maps and (d) archetypal analysis methods. Then evaluate prediction accuracies for global and subspaces calibration models. These methods were tested on a mid-infrared spectral library containing 1907 soil samples collected from 19 different countries under the Africa Soil Information Service project. Calibration models for pH, Mehlich-3 Ca, Mehlich-3 Al, total carbon and clay soil properties were developed for the whole library and for the subspace. Root mean square error of prediction was used to evaluate predictive performance of subspace and global models. The root mean square error of prediction was computed using a one-third-holdout validation set. Effect of pretreating spectra with different methods was tested for 1st and 2nd derivative Savitzky–Golay algorithm, multiplicative scatter correction, standard normal variate and standard normal variate followed by detrending methods. In summary, the results show that global models outperformed the subspace models. We, therefore, conclude that global models are more accurate than the local models except in few cases. For instance, sand and clay root mean square error values from local models from archetypal analysis method were 50% poorer than the global models except for subspace models obtained using multiplicative scatter corrected spectra with which were 12% better. However, the subspace approach provides novel methods for discovering data pattern that may exist in large spectral libraries. PMID:27110048
Fetal asphyctic preconditioning alters the transcriptional response to perinatal asphyxia
2014-01-01
Background Genomic reprogramming is thought to be, at least in part, responsible for the protective effect of brain preconditioning. Unraveling mechanisms of this endogenous neuroprotection, activated by preconditioning, is an important step towards new clinical strategies for treating asphyctic neonates. Therefore, we investigated whole-genome transcriptional changes in the brain of rats which underwent perinatal asphyxia (PA), and rats where PA was preceded by fetal asphyctic preconditioning (FAPA). Offspring were sacrificed 6 h and 96 h after birth, and whole-genome transcription was investigated using the Affymetrix Gene1.0ST chip. Microarray data were analyzed with the Bioconductor Limma package. In addition to univariate analysis, we performed Gene Set Enrichment Analysis (GSEA) in order to derive results with maximum biological relevance. Results We observed minimal, 25% or less, overlap of differentially regulated transcripts across different experimental groups which leads us to conclude that the transcriptional phenotype of these groups is largely unique. In both the PA and FAPA group we observe an upregulation of transcripts involved in cellular stress. Contrastingly, transcripts with a function in the cell nucleus were mostly downregulated in PA animals, while we see considerable upregulation in the FAPA group. Furthermore, we observed that histone deacetylases (HDACs) are exclusively regulated in FAPA animals. Conclusions This study is the first to investigate whole-genome transcription in the neonatal brain after PA alone, and after perinatal asphyxia preceded by preconditioning (FAPA). We describe several genes/pathways, such as ubiquitination and proteolysis, which were not previously linked to preconditioning-induced neuroprotection. Furthermore, we observed that the majority of upregulated genes in preconditioned animals have a function in the cell nucleus, including several epigenetic players such as HDACs, which suggests that epigenetic
Reduction in postsystolic wall thickening during late preconditioning.
Monnet, Xavier; Lucats, Laurence; Colin, Patrice; Derumeaux, Geneviève; Dubois-Rande, Jean-Luc; Hittinger, Luc; Ghaleh, Bijan; Berdeaux, Alain
2007-01-01
Brief coronary artery occlusion (CAO) and reperfusion induce myocardial stunning and late preconditioning. Postsystolic wall thickening (PSWT) also develops with CAO and reperfusion. However, the time course of PSWT during stunning and the regional function pattern of the preconditioned myocardium remain unknown. The goal of this study was to investigate the evolution of PSWT during myocardial stunning and its modifications during late preconditioning. Dogs were chronically instrumented to measure (sonomicrometry) systolic wall thickening (SWT), PSWT, total wall thickening (TWT = SWT + PSWT), and maximal rate of thickening (dWT/dt(max)). Two 10-min CAO (circumflex artery) were performed 24 h apart (day 0 and day 1, n = 7). At day 0, CAO decreased SWT and increased PSWT. During the first hours of the subsequent stunning, evolution of PSWT was symmetrical to that of SWT. At day 1, baseline SWT was similar to day 0, but PSWT was reduced (-66%), while dWT/dt(max) and SWT/TWT ratio increased (+48 and +14%, respectively). After CAO at day 1, stunning was reduced, indicating late preconditioning. Simultaneously vs. day 0, PSWT was significantly reduced, and dWT/dt(max) as well as SWT/TWT ratio were increased, i.e., a greater part of TWT was devoted to ejection. Similar decrease in PSWT was observed with a nonischemic preconditioning stimulus (rapid ventricular pacing, n = 4). In conclusion, a major contractile adaptation occurs during late preconditioning, i.e., the rate of wall thickening is enhanced and PWST is almost abolished. These phenotype adaptations represent potential approaches for characterizing stunning and late preconditioning with repetitive ischemia in humans. PMID:16920813
Sensitivity analysis of a nonlinear Newton-Krylov solver for heat transfer with phase change.
Henninger, Rudolph J.; Knoll, D. A.; Kothe, D. B.; Lally, B. R.
2002-01-01
Development of a complex metal-casting computer model requires information about how varying the problem parameters affects the results (metal flow and solidification). For example, we would like to know how the last point to solidify or the cooling rate at a given location changes when the physical properties of the metal, boundary conditions, or mold geometry are changed. As a preliminary step towards a complete sensitivity analysis of a three-dimensional casting simulation, we examine a one-dimensional version of a metal-alloy phase-change conductive-heat-transfer model by means of Automatic Differentiation (AD). This non-linear 'Jacobian-free' method is a combination of an outer Newton-based iteration and an inner conjugate gradient-like (Krylov) iteration. The implicit solution algorithm has enthalpy as the dependent variable from which temperatures are determined. We examine the sensitivities of the difference between an exact analytical solution for the final temperature and that produced by this algorithm to the problem parameters. In all there are 17 parameters (12 physical constants such as liquid density, heat capacity, and thermal conductivity, 2 initial and boundary condition parameters, the final solution time, and 2 algorithm tolerances). We apply AD in the forward and reverse mode and verify the sensitivities by means of finite differences. In general, the finite-difference method requires at least N+1 computer runs to determine sensitivities for N problem parameters. By forward and reverse, we mean the direction through the solution and in time and space in which the derivative values are obtained. The forward mode is typically more efficient for determining the sensitivity of many responses to one or a few parameters, while the reverse mode is better suited for sensitivities of one or a few responses with respect to many parameters. The sensitivities produced by all the methods agreed to at least three significant figures. The forward and reverse
NASA Astrophysics Data System (ADS)
Hu, Xingzhi; Parks, Geoffrey T.; Chen, Xiaoqian; Seshadri, Pranay
2016-03-01
Uncertainty quantification has recently been receiving much attention from aerospace engineering community. With ever-increasing requirements for robustness and reliability, it is crucial to quantify multidisciplinary uncertainty in satellite system design which dominates overall design direction and cost. However, coupled multi-disciplines and cross propagation hamper the efficiency and accuracy of high-dimensional uncertainty analysis. In this study, an uncertainty quantification methodology based on active subspaces is established for satellite conceptual design. The active subspace effectively reduces the dimension and measures the contributions of input uncertainties. A comprehensive characterization of associated uncertain factors is made and all subsystem models are built for uncertainty propagation. By integrating a system decoupling strategy, the multidisciplinary uncertainty effect is efficiently represented by a one-dimensional active subspace for each design. The identified active subspace is checked by bootstrap resampling for confidence intervals and verified by Monte Carlo propagation for the accuracy. To show the performance of active subspaces, 18 uncertainty parameters of an Earth observation small satellite are exemplified and then another 5 design uncertainties are incorporated. The uncertainties that contribute the most to satellite mass and total cost are ranked, and the quantification of high-dimensional uncertainty is achieved by a relatively small number of support samples. The methodology with considerably less cost exhibits high accuracy and strong adaptability, which provides a potential template to tackle multidisciplinary uncertainty in practical satellite systems.
Modified principal component analysis: an integration of multiple similarity subspace models.
Fan, Zizhu; Xu, Yong; Zuo, Wangmeng; Yang, Jian; Tang, Jinhui; Lai, Zhihui; Zhang, David
2014-08-01
We modify the conventional principal component analysis (PCA) and propose a novel subspace learning framework, modified PCA (MPCA), using multiple similarity measurements. MPCA computes three similarity matrices exploiting the similarity measurements: 1) mutual information; 2) angle information; and 3) Gaussian kernel similarity. We employ the eigenvectors of similarity matrices to produce new subspaces, referred to as similarity subspaces. A new integrated similarity subspace is then generated using a novel feature selection approach. This approach needs to construct a kind of vector set, termed weak machine cell (WMC), which contains an appropriate number of the eigenvectors spanning the similarity subspaces. Combining the wrapper method and the forward selection scheme, MPCA selects a WMC at a time that has a powerful discriminative capability to classify samples. MPCA is very suitable for the application scenarios in which the number of the training samples is less than the data dimensionality. MPCA outperforms the other state-of-the-art PCA-based methods in terms of both classification accuracy and clustering result. In addition, MPCA can be applied to face image reconstruction. MPCA can use other types of similarity measurements. Extensive experiments on many popular real-world data sets, such as face databases, show that MPCA achieves desirable classification results, as well as has a powerful capability to represent data. PMID:25050950
Ischemic Preconditioning in White Matter: Magnitude and Mechanism
Hamner, Margaret A.; Ye, Zucheng; Lee, Richard V.; Colman, Jamie R.; Le, Thu; Gong, Davin C.; Weinstein, Jonathan R.
2015-01-01
Ischemic preconditioning (IPC) is a robust neuroprotective phenomenon whereby brief ischemic exposure confers tolerance to a subsequent ischemic challenge. IPC has not been studied selectively in CNS white matter (WM), although stroke frequently involves WM. We determined whether IPC is present in WM and, if so, its mechanism. We delivered a brief in vivo preconditioning ischemic insult (unilateral common carotid artery ligation) to 12- to 14-week-old mice and determined WM ischemic vulnerability [oxygen–glucose deprivation (OGD)] 72 h later, using acutely isolated optic nerves (CNS WM tracts) from the preconditioned (ipsilateral) and control (contralateral) hemispheres. Functional and structural recovery was assessed by quantitative measurement of compound action potentials (CAPs) and immunofluorescent microscopy. Preconditioned mouse optic nerves (MONs) showed better functional recovery after OGD than the non-preconditioned MONs (31 ± 3 vs 17 ± 3% normalized CAP area, p < 0.01). Preconditioned MONs also showed improved axon integrity and reduced oligodendrocyte injury compared with non-preconditioned MONs. Toll-like receptor-4 (TLR4) and type 1 interferon receptor (IFNAR1), key receptors in innate immune response, are implicated in gray matter preconditioning. Strikingly, IPC-mediated WM protection was abolished in both TLR4−/− and IFNAR1−/− mice. In addition, IPC-mediated protection in WM was also abolished in IFNAR1fl/fl LysMcre, but not in IFNAR1fl/fl control, mice. These findings demonstrated for the first time that IPC was robust in WM, the phenomenon being intrinsic to WM itself. Furthermore, WM IPC was dependent on innate immune cell signaling pathways. Finally, these data demonstrated that microglial-specific expression of IFNAR1 plays an indispensable role in WM IPC. SIGNIFICANCE STATEMENT Ischemic preconditioning (IPC) has been studied predominantly in gray matter, but stroke in humans frequently involves white matter (WM) as well. Here we