It is well known that for singular inconsistent range-symmetric linear systems, the generalized minimal residual (GMRES) method determines a least squares solution without breakdown. The reached least squares solution may be or not be the pseudoinverse solution. We show that a lift strategy can be used to obtain the pseudoinverse solution. In addition, we propose a new iterative method named RSMAR (minimum $\mathbf A$-residual) for range-symmetric linear systems $\mathbf A\mathbf x=\mathbf b$. At step $k$ RSMAR minimizes $\|\mathbf A\mathbf r_k\|$ in the $k$th Krylov subspace generated with $\{\mathbf A, \mathbf r_0\}$ rather than $\|\mathbf r_k\|$, where $\mathbf r_k$ is the $k$th residual vector and $\|\cdot\|$ denotes the Euclidean vector norm. We show that RSMAR and GMRES terminate with the same least squares solution when applied to range-symmetric linear systems. We provide two implementations for RSMAR. Our numerical experiments show that RSMAR is the most suitable method among GMRES-type methods for singular inconsistent range-symmetric linear systems.
相關內容
A module of a graph G is a set of vertices that have the same set of neighbours outside. Modules of a graphs form a so-called partitive family and thereby can be represented by a unique tree MD(G), called the modular decomposition tree. Motivated by the central role of modules in numerous algorithmic graph theory questions, the problem of efficiently computing MD(G) has been investigated since the early 70's. To date the best algorithms run in linear time but are all rather complicated. By combining previous algorithmic paradigms developed for the problem, we are able to present a simpler linear-time that relies on very simple data-structures, namely slice decomposition and sequences of rooted ordered trees.
Sylvester matrix equations are ubiquitous in scientific computing. However, few solution techniques exist for their generalized multiterm version, as they now arise in an increasingly large number of applications. In this work, we consider algebraic parameter-free preconditioning techniques for the iterative solution of generalized multiterm Sylvester equations. They consist in constructing low Kronecker rank approximations of either the operator itself or its inverse. While the former requires solving standard Sylvester equations in each iteration, the latter only requires matrix-matrix multiplications, which are highly optimized on modern computer architectures. Moreover, low Kronecker rank approximate inverses can be easily combined with sparse approximate inverse techniques, thereby enhancing their performance with little or no damage to their effectiveness.
The variational quantum eigensolver (VQE) is a promising candidate that brings practical benefits from quantum computing. However, the required bandwidth in/out of a cryostat is a limiting factor to scale cryogenic quantum computers. We propose a tailored counter-based module with single flux quantum circuits in 4-K stage which precomputes a part of VQE calculation and reduces the amount of inter-temperature communication. The evaluation shows that our system reduces the required bandwidth by 97%, and with this drastic reduction, total power consumption is reduced by 93% in the case where 277 VQE programs are executed in parallel on a 10000-qubit machine.
We introduce so-called functional input neural networks defined on a possibly infinite dimensional weighted space with values also in a possibly infinite dimensional output space. To this end, we use an additive family to map the input weighted space to the hidden layer, on which a non-linear scalar activation function is applied to each neuron, and finally return the output via some linear readouts. Relying on Stone-Weierstrass theorems on weighted spaces, we can prove a global universal approximation result on weighted spaces for continuous functions going beyond the usual approximation on compact sets. This then applies in particular to approximation of (non-anticipative) path space functionals via functional input neural networks. As a further application of the weighted Stone-Weierstrass theorem we prove a global universal approximation result for linear functions of the signature. We also introduce the viewpoint of Gaussian process regression in this setting and emphasize that the reproducing kernel Hilbert space of the signature kernels are Cameron-Martin spaces of certain Gaussian processes. This paves a way towards uncertainty quantification for signature kernel regression.
This paper presents a method for thematic agreement assessment of geospatial data products of different semantics and spatial granularities, which may be affected by spatial offsets between test and reference data. The proposed method uses a multi-scale framework allowing for a probabilistic evaluation whether thematic disagreement between datasets is induced by spatial offsets due to different nature of the datasets or not. We test our method using real-estate derived settlement locations and remote-sensing derived building footprint data.
We present an asymptotic-preserving (AP) numerical method for solving the three-temperature radiative transfer model, which holds significant importance in inertial confinement fusion. A carefully designedsplitting method is developed that can provide a general framework of extending AP schemes for the gray radiative transport equation to the more complex three-temperature radiative transfer model. The proposed scheme captures two important limiting models: the three-temperature radiation diffusion equation (3TRDE) when opacity approaches infinity and the two-temperature limit when the ion-electron coupling coefficient goes to infinity. We have rigorously demonstrated the AP property and energy conservation characteristics of the proposed scheme and its efficiency has been validated through a series of benchmark tests in the numerical part.
In an error estimation of finite element solutions to the Poisson equation, we usually impose the shape regularity assumption on the meshes to be used. In this paper, we show that even if the shape regularity condition is violated, the standard error estimation can be obtained if "bad" elements (elements that violate the shape regularity or maximum angle condition) are covered virtually by "good" simplices. A numerical experiment confirms the theoretical result.
We derive sharp-interface models for one-dimensional brittle fracture via the inverse-deformation approach. Methods of Gamma-convergence are employed to obtain the singular limits of previously proposed models. The latter feature a local, non-convex stored energy of inverse strain, augmented by small interfacial energy, formulated in terms of the inverse-strain gradient. They predict spontaneous fracture with exact crack-opening discontinuities, without the use of damage (phase) fields or pre-existing cracks; crack faces are endowed with a thin layer of surface energy. The models obtained herewith inherit the same properties, except that surface energy is now concentrated at the crack faces. Accordingly, we construct energy-minimizing configurations. For a composite bar with a breakable layer, our results predict a pattern of equally spaced cracks whose number is given as an increasing function of applied load.
We present a new method to compute the solution to a nonlinear tensor differential equation with dynamical low-rank approximation. The idea of dynamical low-rank approximation is to project the differential equation onto the tangent space of a low-rank tensor manifold at each time. Traditionally, an orthogonal projection onto the tangent space is employed, which is challenging to compute for nonlinear differential equations. We introduce a novel interpolatory projection onto the tangent space that is easily computed for many nonlinear differential equations and satisfies the differential equation at a set of carefully selected indices. To select these indices, we devise a new algorithm based on the discrete empirical interpolation method (DEIM) that parameterizes any tensor train and its tangent space with tensor cross interpolants. We demonstrate the proposed method with applications to tensor differential equations arising from the discretization of partial differential equations.
We hypothesize that due to the greedy nature of learning in multi-modal deep neural networks, these models tend to rely on just one modality while under-fitting the other modalities. Such behavior is counter-intuitive and hurts the models' generalization, as we observe empirically. To estimate the model's dependence on each modality, we compute the gain on the accuracy when the model has access to it in addition to another modality. We refer to this gain as the conditional utilization rate. In the experiments, we consistently observe an imbalance in conditional utilization rates between modalities, across multiple tasks and architectures. Since conditional utilization rate cannot be computed efficiently during training, we introduce a proxy for it based on the pace at which the model learns from each modality, which we refer to as the conditional learning speed. We propose an algorithm to balance the conditional learning speeds between modalities during training and demonstrate that it indeed addresses the issue of greedy learning. The proposed algorithm improves the model's generalization on three datasets: Colored MNIST, Princeton ModelNet40, and NVIDIA Dynamic Hand Gesture.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191