2024-10-29 | | Total: 30
Nowadays, we have seen that dual quaternion algorithms are used in 3D coordinate transformation problems due to their advantages. 3D coordinate transformation problem is one of the important problems in geodesy. This transformation problem is encountered in many application areas other than geodesy. Although there are many coordinate transformation methods (similarity, affine, projective, etc.), similarity transformation is used because of its simplicity. The asymmetric transformation is preferred to the symmetric coordinate transformation because of its ease of use. In terms of error theory, the symmetric transformation should be preferred. In this study, the topic of symmetric similarity 3D coordinate transformation based on the dual quaternion algorithm is discussed, and the bottlenecks encountered in solving the problem and the solution method are discussed. A new iterative algorithm based on the dual quaternion is presented. The solution is implemented in two different models: with constraint equations and without constraint equations. The advantages and disadvantages of the two models compared to each other are also evaluated. Not only the transformation parameters but also the errors of the transformation parameters are determined. The detailed derivation of the formulas for estimating the symmetric similarity of 3D transformation parameters is presented step by step. Since symmetric transformation is the general form of asymmetric transformation, we can also obtain asymmetric transformation results with a simple modification of the model we developed for symmetric transformation. The proposed algorithm is capable of performing both 2D and 3D symmetric and asymmetric similarity transformations. For the 2D transformation, it is sufficient to replace the z and Z coordinates in both systems with zero.
Seam carving, a content-aware image resizing technique, has garnered significant attention for its ability to resize images while preserving important content. In this paper, we conduct a comprehensive analysis of four algorithmic design techniques for seam carving: brute-force, greedy, dynamic programming, and GPU-based parallel algorithms. We begin by presenting a theoretical overview of each technique, discussing their underlying principles and computational complexities. Subsequently, we delve into empirical evaluations, comparing the performance of these algorithms in terms of runtime efficiency. Our experimental results provide insights into the theoretical complexities of the design techniques.
We develop a new spatial semidiscrete multiscale method based upon the edge multiscale methods to solve semilinear parabolic problems with heterogeneous coefficients and smooth initial data. This method allows for a cheap spatial discretization, which fails to resolve the spatial heterogeneity but maintains satisfactory accuracy independent of the heterogeneity. This is achieved by simultaneously constructing a steady-state multiscale ansatz space with certain approximation properties for the evolving solution and the initial data. The approximation properties of the multiscale ansatz space are derived using local-global splitting. A fully discrete scheme is analyzed using a first-order explicit exponential Euler scheme. We derive the error estimates in the $L^{2}$-norm and energy norm under the regularity assumptions for the semilinear term. The convergence rates depend on the coarse grid size and the level parameter. Finally, extensive numerical experiments are carried out to validate the efficiency of the proposed method.
In this paper, we propose a new class of splitting methods to solve the stochastic Langevin equation, which can simultaneously preserve the ergodicity and exponential integrability of the original equation. The central idea is to extract a stochastic subsystem that possesses the strict dissipation from the original equation, which is inspired by the inheritance of the Lyapunov structure for obtaining the ergodicity. We prove that the exponential moment of the numerical solution is bounded, thus validating the exponential integrability of the proposed methods. Further, we show that under moderate verifiable conditions, the methods have the first-order convergence in both strong and weak senses, and we present several concrete splitting schemes based on the methods. The splitting strategy of methods can be readily extended to construct conformal symplectic methods and high-order methods that preserve both the ergodicity and the exponential integrability, as demonstrated in numerical experiments. Our numerical experiments also show that the proposed methods have good performance in the long-time simulation.
We propose numerical schemes for the approximate solution of problems defined on the edges of a one-dimensional graph. In particular, we consider linear transport and a drift-diffusion equations, and discretize them by extending Finite Volume schemes with upwind flux to domains presenting bifurcation nodes with an arbitrary number of incoming and outgoing edges, and implicit time discretization. We show that the discrete problems admit positive unique solutions, and we test the methods on the intricate geometry of an electrical treeing.
This paper presents a projection-based reduced order modelling (ROM) framework for unsteady parametrized optimal control problems (OCP$_{(\mu)}$s) arising from cardiovascular (CV) applications. In real-life scenarios, accurately defining outflow boundary conditions in patient-specific models poses significant challenges due to complex vascular morphologies, physiological conditions, and high computational demands. These challenges make it difficult to compute realistic and reliable CV hemodynamics by incorporating clinical data such as 4D magnetic resonance imaging. To address these challenges, we focus on controlling the outflow boundary conditions to optimize CV flow dynamics and minimize the discrepancy between target and computed flow velocity profiles. The fluid flow is governed by unsteady Navier--Stokes equations with physical parametric dependence, i.e. the Reynolds number. Numerical solutions of OCP$_{(\mu)}$s require substantial computational resources, highlighting the need for robust and efficient ROMs to perform real-time and many-query simulations. Here, we aim at investigating the performance of a projection-based reduction technique that relies on the offline-online paradigm, enabling significant computational cost savings. The Galerkin finite element method is used to compute the high-fidelity solutions in the offline phase. We implemented a nested-proper orthogonal decomposition (nested-POD) for fast simulation of OCP$_{(\mu)}$s that encompasses two stages: temporal compression for reducing dimensionality in time, followed by parametric-space compression on the precomputed POD modes. We tested the efficacy of the methodology on vascular models, namely an idealized bifurcation geometry and a patient-specific coronary artery bypass graft, incorporating stress control at the outflow boundary, observing consistent speed-up with respect to high-fidelity strategies.
This paper is concerned about the implicit-explicit (IMEX) methods for a class of dissipative wave systems with time-varying velocity feedbacks and nonlinear potential energies, equipped with different boundary conditions. Firstly, we approximate the problems by using a vanilla IMEX method, which is a second-order scheme for the problems when the damping terms are time-independent. However, rigors analysis shows that the error rate declines from second to first order due to the nonautonomous dampings. To recover the convergence order, we propose a revised IMEX scheme and apply it to the nonautonomous wave equations with a kinetic boundary condition. Our numerical experiments demonstrate that the revised scheme can not only achieve second-order accuracy but also improve the computational efficiency.
We design and analyse an energy stable, structure preserving and well-balanced scheme for the Ripa system of shallow water equations. The energy stability of the numerical solutions is achieved by introducing appropriate stabilisation terms in the discretisation of the convective fluxes of mass and momenta, the pressure gradient and the topography source term. A diligent choice of the interface values of the water height and the temperature ensures the well-balancing property of the scheme for three physically relevant hydrostatic steady states. The explicit in time and finite volume in space scheme preserves the positivity of the water height and the temperature, and it is weakly consistent with the continuous model equations in the sense of Lax-Wendroff. The results of extensive numerical case studies on benchmark test problems are presented to confirm the theoretical findings.
This paper presents an efficient weak Galerkin (WG) finite element method with reduced stabilizers for solving the time-harmonic Maxwell equations on both convex and non-convex polyhedral meshes. By employing bubble functions as a critical analytical tool, the proposed method enhances efficiency by partially eliminating the stabilizers traditionally used in WG methods. This streamlined WG method demonstrates stability and effectiveness on convex and non-convex polyhedral meshes, representing a significant improvement over existing stabilizer-free WG methods, which are typically limited to convex elements within finite element partitions. The method achieves an optimal error estimate for the exact solution in a discrete $H^1$ norm, and additionally, an optimal $L^2$ error estimate is established for the WG solution. Several numerical experiments are conducted to validate the method's efficiency and accuracy.
The paper introduces a novel tangential-normal ($t$-$n$) decomposition for finite element differential forms. Its main contribution is the development of a $t$-$n$ basis where the degrees of freedom and shape functions are explicitly dual to each other. This duality simplifies the assembly of stiffness matrices and enhances the efficiency of interpolation and numerical integration in finite element methods. Additionally, the well-documented Lagrange element basis can be used to expedite implementation. This paper focuses on the full polynomial spaces, excluding trimmed polynomial differential forms, and provides a new perspective on constructing finite element differential forms.
This paper presents a numerical method to solve a time-fractional Burgers equation, achieving order of convergence $(2-\alpha)$ in time, here $\alpha$ represents the order of the time derivative. The fractional derivative is modeled by Caputo-Prabhakar (CP) formulation, which incorporates a kernel defined by the three-parameter Mittag-Leffler function. Finite difference methods are employed for the discretization of the derivatives. To handle the non-linear term, the Newton iteration method is used. The proposed numerical scheme is proven to be stable and convergent in the $L_{\infty}$ norm. The validity of the theory is supported by two numerical examples.
In this work, we first present an adaptive deterministic block coordinate descent method with momentum (mADBCD) to solve the linear least-squares problem, which is based on Polyak's heavy ball method and a new column selection criterion for a set of block-controlled indices defined by the Euclidean norm of the residual vector of the normal equation. The mADBCD method eliminates the need for pre-partitioning the column indexes of the coefficient matrix, and it also obviates the need to compute the Moore-Penrose pseudoinverse of a column sub-matrix at each iteration. Moreover, we demonstrate the adaptability and flexibility in the automatic selection and updating of the block control index set. When the coefficient matrix has full rank, the theoretical analysis of the mADBCD method indicates that it linearly converges towards the unique solution of the linear least-squares problem. Furthermore, by effectively integrating count sketch technology with the mADBCD method, we also propose a novel count sketch adaptive block coordinate descent method with momentum (CS-mADBCD) for solving highly overdetermined linear least-squares problems and analysis its convergence. Finally, numerical experiments illustrate the advantages of the proposed two methods in terms of both CPU times and iteration counts compared to recent block coordinate descent methods.
We present results of a long-term team collaboration of mathematicians and biologists. We focus on building a mathematical framework for the shape space constituted by a collection of homologous bones or teeth from many species. The biological application is to quantitative morphological understanding of the evolutionary history of primates in particular, and mammals more generally. Similar to the practice of biologists, we leverage the power of the whole collection for results that are more robust than can be obtained by only pairwise comparisons, using tools from differential geometry and machine learning. This paper concentrates on the mathematical framework. We review methods for comparing anatomical surfaces, discuss the problem of registration and alignment, and address the computation of different distances. Next, we cover broader questions related to cross-dataset landmark selection, shape segmentation, and shape classification analysis. This paper summarizes the work of many team members other than the authors; in this paper that unites (for the first time) all their results in one joint context, space restrictions prevent a full description of the mathematical details, which are thoroughly covered in the original articles. Although our application is to the study of anatomical surfaces, we believe our approach has much wider applicability.
Many natural and manufactured structures can be effectively modeled as networks of one dimensional segments joined at nodes. A new algorithm for the numerical solution of various time dependent partial differential equations on some of these networks is presented. The main novelty is a network version of the Fast Fourier Transform, which provides an efficient technique for expansions with eigenfunctions of the Laplace operator.
Potential-driven steady-state flow in networks is an abstract problem which manifests in various engineering applications, such as transport of natural gas, water, electric power through infrastructure networks or flow through fractured rocks modelled as discrete fracture networks. In general, while the problem is simple when restricted to a single edge of a network, it ceases to be so for a large network. The resultant system of nonlinear equations depends on the network topology and in general there is no numerical algorithm that offers guaranteed convergence to the solution (assuming a solution exists). Some methods offer guarantees in cases where the network topology satisfies certain assumptions but these methods fail for larger networks. On the other hand, the Newton-Raphson algorithm offers a convergence guarantee if the starting point lies close to the (unknown) solution. It would be advantageous to compute the solution of the large nonlinear system through the solution of smaller nonlinear sub-systems wherein the solution algorithms (Newton-Raphson or otherwise) are more likely to succeed. This article proposes and describes such a procedure, an hierarchical network partitioning algorithm that enables the solution of large nonlinear systems corresponding to potential-driven steady-state network flow equations.
Inverse problems arise in many applications, especially tomographic imaging. We develop a Learned Alternating Minimization Algorithm (LAMA) to solve such problems via two-block optimization by synergizing data-driven and classical techniques with proven convergence. LAMA is naturally induced by a variational model with learnable regularizers in both data and image domains, parameterized as composite functions of neural networks trained with domain-specific data. We allow these regularizers to be nonconvex and nonsmooth to extract features from data effectively. We minimize the overall objective function using Nesterov's smoothing technique and residual learning architecture. It is demonstrated that LAMA reduces network complexity, improves memory efficiency, and enhances reconstruction accuracy, stability, and interpretability. Extensive experiments show that LAMA significantly outperforms state-of-the-art methods on popular benchmark datasets for Computed Tomography.
Deriving sharp and computable upper bounds of the Lipschitz constant of deep neural networks is crucial to formally guarantee the robustness of neural-network based models. We analyse three existing upper bounds written for the $l^2$ norm. We highlight the importance of working with the $l^1$ and $l^\infty$ norms and we propose two novel bounds for both feed-forward fully-connected neural networks and convolutional neural networks. We treat the technical difficulties related to convolutional neural networks with two different methods, called explicit and implicit. Several numerical tests empirically confirm the theoretical results, help to quantify the relationship between the presented bounds and establish the better accuracy of the new bounds. Four numerical tests are studied: two where the output is derived from an analytical closed form are proposed; another one with random matrices; and the last one for convolutional neural networks trained on the MNIST dataset. We observe that one of our bound is optimal in the sense that it is exact for the first test with the simplest analytical form and it is better than other bounds for the other tests.
We investigate the convergence of the primal-dual algorithm for composite optimization problems when the objective functions are weakly convex. We introduce a modified duality gap function, which is a lower bound of the standard duality gap function. Under the sharpness condition of this new function, we identify the area around the set of saddle points where we obtain the convergence of the primal-dual algorithm. We give numerical examples and applications in image denoising and deblurring to demonstrate our results.
This paper offers a contemporary and comprehensive perspective on the classical algorithms utilized for the solution of minimum-time problem for linear systems (MTPLS). The use of unified notations supported by visual geometric representations serves to highlight the differences between the Neustadt-Eaton and Barr-Gilbert algorithms. Furthermore, these notations assist in the interpretation of the distance-finding algorithms utilized in the Barr-Gilbert algorithm. Additionally, we present a novel algorithm for solving MTPLS and provide a constructive proof of its convergence. Similar to the Barr-Gilbert algorithm, the novel algorithm employs distance search algorithms. The design of the novel algorithm is oriented towards solving such MTPLS for which the analytic description of the reachable set is available. To illustrate the advantages of the novel algorithm, we utilize the isotropic rocket benchmark. Numerical experiments demonstrate that, for high-precision computations, the novel algorithm outperforms others by factors of tens or hundreds and exhibits the lowest failure rate.
For a square matrix $A$, Gaussian elimination with partial pivoting (GEPP) results in the factorization $PA = LU$ where $L$ and $U$ are lower and upper triangular matrices and $P$ is a permutation matrix. If $A$ is a random matrix, then the associated permutation from the $P$ factor is random. We are interested in studying properties of random permutations generated using GEPP. We introduce and present probabilistic results for groups of simple and nonsimple butterfly permutations of order $N = p^n$ for prime $p$, on which GEPP induces the Haar measure when applied to particular ensembles of random butterfly matrices. Of note, the nonsimple butterfly permutations include specific $p$-Sylow subgroups of $S_{p^n}$ for each prime $p$. Moreover, we focus on addressing the questions of the longest increasing subsequence (LIS) and the number of cycles for butterfly permutations. Our proof techniques utilize the explicit structural recursive properties of these permutations to answer what are traditionally hard analytical questions using simpler tools. For simple butterfly permutations, we provide full distributional descriptions and Law of Large Numbers (LLN) or Central Limit Theorem (CLT) type results for each statistic. For nonsimple $p$-nary butterfly permutations, we establish lower and upper power law bounds on the expected LIS of the form $N^{\alpha_p}$ and $N^{\beta_p}$ where $\frac12 < \alpha_p < \beta_p < 1$ for each $p$ with $\alpha_p = 1 - o_p(1)$. Additionally, we determine the aysmptotic form for the number of cycles scaled by $(2 - \frac1p)^n$ that limit to new distributions we introduce depending only on $p$ whose positive integer moments satisfy explicit recursion formulas for each $p$; in particular, this characterizes a full CLT result for the number of cycles for any uniform $p$-Sylow subgroup of $S_{p^n}$.
Harmful cyanobacterial blooms (CBs) have a growing global prevalence, emerging as a significant environmental concern due to their potential toxicity. Understanding how the different mechanisms affect CBs is crucial to develop actionable management strategies. For this, we derive a stoichiometric dynamical system that describes the qualitative population dynamics of cyanobacteria and their toxicity in north-temperate freshwater ecosystems. Our model quantifies the hypoxic effects of CBs on fish mortality and the effect of microcystin-LR (MC-LR), a potent toxin produced by cyanobacteria, on aquatic macro-invertebrates, phytoplankton, and fish species. By fitting the model to lakes with varying physical characteristics, eutrophic conditions, and water temperature, we can delineate and understand the driving components of CBs. We show that decreases in water exchange rate, depth of epilimnion, or light attenuation increases bloom intensity and duration. Furthermore, our models concur that eutrophication and increasing water temperatures exacerbate the intensity of CBs. We observe a severe bioaccumulative effect of MC-LR in aquatic species, stressing the potential impact on humans and other terrestrial animals. We validate our model with field measurements demonstrating its applicability to several realistic lake conditions. These insights are essential for informing targeted interventions to reduce CBs and their ecological impacts.
Lie symmetry transformations that leave a differential equation invariant play a fundamental role in science and mathematics. Such Lie symmetry groups uniquely determine their Lie symmetry algebras. Exact differential elimination algorithms have been developed to determine the dimension and structure constants of the Lie symmetry algebra of an exact polynomially nonlinear differential equation. Directly applying these symbolic algorithms to approximate models is prone to instability since these algorithms strongly depend on the orderings of the variables involved. This motivates the need to address questions at the algorithmic foundation of approximate Lie symmetry algebras of differential equations. How do we define approximate Lie symmetry? How do we compute and apply approximate Lie symmetry algebras of differential equations? How reliable are the results? To address such questions, we define approximate Lie symmetry algebras in terms of exact Lie symmetry algebras of a nearby differential equation. Our algorithm for identifying these hidden approximate Lie symmetry algebras uses the SVD to find nearby rank-deficient systems combined with approximate geometric involutive forms of the approximate symmetry-defining systems. Our approach is local and depends on an input base point in the space of independent and dependent variables. In general, our local approach can yield many different nearby Lie symmetry algebras. We also outline a numerical approach to determining the approximate isomorphic of such Lie symmetry algebras as the local base point varies across a grid in the base space. We also provide a method for evaluating the reliability of our results. This enables the base space to be partitioned into regions where different local Lie symmetry algebras are admitted, separated by unstable transition regions.
We consider the dynamics of bodies with "active" microstructure described by vectorvalued phase fields. For waves with time-varying amplitude, the associated evolution equation involves a matrix that can be non-normal, depending on the constitutive choices adopted for the microstructural actions associated with the phase field. In the presence of non-normality, the spectral analysis of such a matrix when (unknown or uncertain or time-dependent) constitutive parameters vary is generically not decisive to evaluate the material stability. We thus need to look at the pseudospectrum, that is, the set of all possible eigenvalues of matrices in an {\epsilon}-neighborhood of the matrix of interest. As a case study, we look at quasicrystals and evaluate through spectra and pseudospectra the influence of a microstructural self-action on the material stability. This approach allows us to reliably determine thresholds where stable-unstable transitions in the material behavior occur.
We present a new sampling-based approach for enabling efficient computation of low-rank Bayesian matrix completion and quantifying the associated uncertainty. Firstly, we design a new prior model based on the singular-value-decomposition (SVD) parametrization of low-rank matrices. Our prior is analogous to the seminal nuclear-norm regularization used in non-Bayesian setting and enforces orthogonality in the factor matrices by constraining them to Stiefel manifolds. Then, we design a geodesic Hamiltonian Monte Carlo (-within-Gibbs) algorithm for generating posterior samples of the SVD factor matrices. We demonstrate that our approach resolves the sampling difficulties encountered by standard Gibbs samplers for the common two-matrix factorization used in matrix completion. More importantly, the geodesic Hamiltonian sampler allows for sampling in cases with more general likelihoods than the typical Gaussian likelihood and Gaussian prior assumptions adopted in most of the existing Bayesian matrix completion literature. We demonstrate an applications of our approach to fit the categorical data of a mice protein dataset and the MovieLens recommendation problem. Numerical examples demonstrate superior sampling performance, including better mixing and faster convergence to a stationary distribution. Moreover, they demonstrate improved accuracy on the two real-world benchmark problems we considered.
Pretraining methods gain increasing attraction recently for solving PDEs with neural operators. It alleviates the data scarcity problem encountered by neural operator learning when solving single PDE via training on large-scale datasets consisting of various PDEs and utilizing shared patterns among different PDEs to improve the solution precision. In this work, we propose the Latent Neural Operator Pretraining (LNOP) framework based on the Latent Neural Operator (LNO) backbone. We achieve universal transformation through pretraining on hybrid time-dependent PDE dataset to extract representations of different physical systems and solve various time-dependent PDEs in the latent space through finetuning on single PDE dataset. Our proposed LNOP framework reduces the solution error by 31.7% on four problems and can be further improved to 57.1% after finetuning. On out-of-distribution dataset, our LNOP model achieves roughly 50% lower error and 3$\times$ data efficiency on average across different dataset sizes. These results show that our method is more competitive in terms of solution precision, transfer capability and data efficiency compared to non-pretrained neural operators.