Consider a finite directed graph without cycles in which the arrows are weighted. We present an algorithm for the computation of a new distance, called path-length-weighted distance, which has proven useful for graph analysis in the context of fraud detection. The idea is that the new distance explicitly takes into account the size of the paths in the calculations. Thus, although our algorithm is based on arguments similar to those at work for the Bellman-Ford and Dijkstra methods, it is in fact essentially different. We lay out the appropriate framework for its computation, showing the constraints and requirements for its use, along with some illustrative examples.
相關內容
Motivated by the need for the rigorous analysis of the numerical stability of variational least-squares kernel-based methods for solving second-order elliptic partial differential equations, we provide previously lacking stability inequalities. This fills a significant theoretical gap in the previous work [Comput. Math. Appl. 103 (2021) 1-11], which provided error estimates based on a conjecture on the stability. With the stability estimate now rigorously proven, we complete the theoretical foundations and compare the convergence behavior to the proven rates. Furthermore, we establish another stability inequality involving weighted-discrete norms, and provide a theoretical proof demonstrating that the exact quadrature weights are not necessary for the weighted least-squares kernel-based collocation method to converge. Our novel theoretical insights are validated by numerical examples, which showcase the relative efficiency and accuracy of these methods on data sets with large mesh ratios. The results confirm our theoretical predictions regarding the performance of variational least-squares kernel-based method, least-squares kernel-based collocation method, and our new weighted least-squares kernel-based collocation method. Most importantly, our results demonstrate that all methods converge at the same rate, validating the convergence theory of weighted least-squares in our proven theories.
This paper addresses the inverse scattering problem for Maxwell's equations. We first show that a bianisotropic scatterer can be uniquely determined from multi-static far-field data through the factorization analysis of the far-field operator. Next, we investigate a modified version of the orthogonality sampling method, as proposed in \cite{Le2022}, for the numerical reconstruction of the scatterer. Finally, we apply this sampling method to invert unprocessed 3D experimental data obtained from the Fresnel Institute \cite{Geffrin2009}. Numerical examples with synthetic scattering data for bianisotropic targets are also presented to demonstrate the effectiveness of the method.
A new variant of the GMRES method is presented for solving linear systems with the same matrix and subsequently obtained multiple right-hand sides. The new method keeps such properties of the classical GMRES algorithm as follows. Both bases of the search space and its image are maintained orthonormal that increases the robustness of the method. Moreover there is no need to store both bases since they are effectively represented within a common basis. Along with it our method is theoretically equivalent to the GCR method extended for a case of multiple right-hand sides but is more numerically robust and requires less memory. The main result of the paper is a mechanism of adding an arbitrary direction vector to the search space that can be easily adopted for flexible GMRES or GMRES with deflated restarting.
For several types of information relations, the induced rough sets system RS does not form a lattice but only a partially ordered set. However, by studying its Dedekind-MacNeille completion DM(RS), one may reveal new important properties of rough set structures. Building upon D. Umadevi's work on describing joins and meets in DM(RS), we previously investigated pseudo-Kleene algebras defined on DM(RS) for reflexive relations. This paper delves deeper into the order-theoretic properties of DM(RS) in the context of reflexive relations. We describe the completely join-irreducible elements of DM(RS) and characterize when DM(RS) is a spatial completely distributive lattice. We show that even in the case of a non-transitive reflexive relation, DM(RS) can form a Nelson algebra, a property generally associated with quasiorders. We introduce a novel concept, the core of a relational neighborhood, and use it to provide a necessary and sufficient condition for DM(RS) to determine a Nelson algebra.
Regularization is a critical technique for ensuring well-posedness in solving inverse problems with incomplete measurement data. Traditionally, the regularization term is designed based on prior knowledge of the unknown signal's characteristics, such as sparsity or smoothness. Inhomogeneous regularization, which incorporates a spatially varying exponent $p$ in the standard $\ell_p$-norm-based framework, has been used to recover signals with spatially varying features. This study introduces weighted inhomogeneous regularization, an extension of the standard approach incorporating a novel exponent design and spatially varying weights. The proposed exponent design mitigates misclassification when distinct characteristics are spatially close, while the weights address challenges in recovering regions with small-scale features that are inadequately captured by traditional $\ell_p$-norm regularization. Numerical experiments, including synthetic image reconstruction and the recovery of sea ice data from incomplete wave measurements, demonstrate the effectiveness of the proposed method.
The phenomenon of finite time blow-up in hydrodynamic partial differential equations is central in analysis and mathematical physics. While numerical studies have guided theoretical breakthroughs, it is challenging to determine if the observed computational results are genuine or mere numerical artifacts. Here we identify numerical signatures of blow-up. Our study is based on the complexified Euler equations in two dimensions, where instant blow-up is expected. Via a geometrically consistent spatiotemporal discretization, we perform several numerical experiments and verify their computational stability. We then identify a signature of blow-up based on the growth rates of the supremum norm of the vorticity with increasing spatial resolution. The study aims to be a guide for cross-checking the validity for future numerical experiments of suspected blow-up in equations where the analysis is not yet resolved.
The dynamics of magnetization in ferromagnetic materials are modeled by the Landau-Lifshitz equation, which presents significant challenges due to its inherent nonlinearity and non-convex constraint. These complexities necessitate efficient numerical methods for micromagnetics simulations. The Gauss-Seidel Projection Method (GSPM), first introduced in 2001, is among the most efficient techniques currently available. However, existing GSPMs are limited to first-order accuracy. This paper introduces two novel second-order accurate GSPMs based on a combination of the biharmonic equation and the second-order backward differentiation formula, achieving computational complexity comparable to that of solving the scalar biharmonic equation implicitly. The first proposed method achieves unconditional stability through Gauss-Seidel updates, while the second method exhibits conditional stability with a Courant-Friedrichs-Lewy constant of 0.25. Through consistency analysis and numerical experiments, we demonstrate the efficacy and reliability of these methods. Notably, the first method displays unconditional stability in micromagnetics simulations, even when the stray field is updated only once per time step.
An injective colouring of a graph is a colouring in which every two vertices sharing a common neighbour receive a different colour. Chen, Hahn, Raspaud and Wang conjectured that every planar graph of maximum degree $\Delta \ge 3$ admits an injective colouring with at most $\lfloor 3\Delta/2\rfloor$ colours. This was later disproved by Lu\v{z}ar and \v{S}krekovski for certain small and even values of $\Delta$ and they proposed a new refined conjecture. Using an algorithm for determining the injective chromatic number of a graph, i.e. the smallest number of colours for which the graph admits an injective colouring, we give computational evidence for Lu\v{z}ar and \v{S}krekovski's conjecture and extend their results by presenting an infinite family of $3$-connected planar graphs for each $\Delta$ (except for $4$) attaining their bound, whereas they only gave a finite amount of examples for each $\Delta$. Hence, together with another infinite family of maximum degree $4$, we provide infinitely many counterexamples to the conjecture by Chen et al. for each $\Delta$ if $4\le \Delta \le 7$ and every even $\Delta \ge 8$. We provide similar evidence for analogous conjectures by La and \v{S}torgel and Lu\v{z}ar, \v{S}krekovski and Tancer when the girth is restricted as well. Also in these cases we provide infinite families of $3$-connected planar graphs attaining the bounds of these conjectures for certain maximum degrees $\Delta\geq 3$.
We propose and analyze a space--time finite element method for Westervelt's quasilinear model of ultrasound waves in second-order formulation. The method combines conforming finite element spatial discretizations with a discontinuous-continuous Galerkin time stepping. Its analysis is challenged by the fact that standard Galerkin testing approaches for wave problems do not allow for bounding the discrete energy at all times. By means of redesigned energy arguments for a linearized problem combined with Banach's fixed-point argument, we show the well-posedness of the scheme, a priori error estimates, and robustness with respect to the strong damping parameter $\delta$. Moreover, the scheme preserves the asymptotic preserving property of the continuous problem; more precisely, we prove that the discrete solutions corresponding to $\delta>0$ converge, in the singular vanishing dissipation limit, to the solution of the discrete inviscid problem. We use several numerical experiments in $(2 + 1)$-dimensions to validate our theoretical results.
Unlabeled sensing is a linear inverse problem with permuted measurements. We propose an alternating minimization (AltMin) algorithm with a suitable initialization for two widely considered permutation models: partially shuffled/$k$-sparse permutations and $r$-local/block diagonal permutations. Key to the performance of the AltMin algorithm is the initialization. For the exact unlabeled sensing problem, assuming either a Gaussian measurement matrix or a sub-Gaussian signal, we bound the initialization error in terms of the number of blocks $s$ and the number of shuffles $k$. Experimental results show that our algorithm is fast, applicable to both permutation models, and robust to choice of measurement matrix. We also test our algorithm on several real datasets for the linked linear regression problem and show superior performance compared to baseline methods.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191