Center for Computational and Stochastic Mathematics

Funder

Organizational Unit

Publications

The existential transversal property: a generalization of homogeneity and its impact on semigroups

Publication . Araújo, João; Bentz, Wolfram; Cameron, Peter

Let G be a permutation group of degree n, and k a positive integer with k ≤ n. We say that G has the k-existential transversal property, or k-et, if there exists a k-subset A (of the domain Ω) whose orbit un- der G contains transversals for all k-partitions P of Ω. This property is a substantial weakening of the k-universal transversal property, or k-ut, investigated by the first and third author, which required this condition to hold for all k-subsets A of the domain Ω. Our first task in this paper is to investigate the k-et property and to decide which groups satisfy it. For example, it is known that for k < 6 there are several families of k-transitive groups, but for k ≥ 6 the only ones are alternating or symmetric groups; here we show that in the k-et context the threshold is 8, that is, for 8 ≤ k ≤ n/2, the only transitive groups with k-et are the symmetric and alternating groups; this is best possible since the Mathieu group M24 (degree 24) has 7-et. We determine all groups with k-et for 4 ≤ k ≤ n/2, up to some unresolved cases for k = 4, 5, and describe the property for k = 2, 3 in permutation group language. These considerations essentially answer Problem 5 proposed in the paper on k-ut referred to above; we also slightly improve the classification of groups possessing the k-ut property. In that earlier paper, the results were applied to semigroups, in particular, to the question of when the semigroup 〈G, t〉 is regular, where t is a map of rank k (with k < n/2); this turned out to be equivalent to the k-ut property. The question investigated here is when there is a k-subset A of the domain such that 〈G, t〉 is regular for all maps t with image A. This turns out to be much more delicate; the k-et property (with A as witnessing set) is a necessary condition, and the combination of k-et and (k − 1)-ut is sufficient, but the truth lies somewhere between. Given the knowledge that a group under consideration has the necessary condition of k-et, the regularity question for k ≤ n/2 is solved except for one sporadic group. The paper ends with a number of problems on combinatorics, permutation groups and transformation semigroups, and their linear analogues.

2021Journal article

Restricted access

Primitive permutation groups and strongly factorizable transformation semigroups

Publication . Araújo, João; Bentz, Wolfram; Cameron, Peter

Let Ω be a finite set and T (Ω) be the full transformation monoid on Ω. The rank of a transformation t ∈ T (Ω) is the natural number |Ωt|. Given A ⊆ T (Ω), denote by 〈A〉 the semigroup generated by A. Let k be a fixed natural number such that 2 ≤ k ≤ |Ω|. In the first part of this paper we (almost) classify the permutation groups G on Ω such that for all rank k transformations t ∈ T (Ω), every element in St := 〈G, t〉 can be written as a product eg, where e2 = e ∈ St and g ∈ G. In the second part we prove, among other results, that if S ≤ T (Ω) and G is the normalizer of S in the symmetric group on Ω, then the semigroup SG is regular if and only if S is regular. (Recall that a semigroup S is regular if for all s ∈ S there exists s′ ∈ S such that s = ss′s.) The paper ends with a list of problems.

2021-01-01Journal article

Open access

Improving the conditioning of the method of fundamental solutions for the Helmholtz equation on domains in polar or elliptic coordinates

Publication . Antunes, Pedro R. S.; Calunga, Hernani; Serranho, Pedro

A new approach to overcome the ill-conditioning of the Method of Fundamental Solutions (MFS) combining Singular Value Decomposition (SVD) and an adequate change of basis was introduced in [1] as MFS-SVD. The original formulation considered polar coordinates and harmonic polynomials as basis functions and is restricted to the Laplace equation in 2D. In this work, we start by adapting the approach to the Helmholtz equation in 2D and later extending it to elliptic coordinates. As in the Laplace case, the approach in polar coordinates has very good numerical results both in terms of conditioning and accuracy for domains close to a disk but does not perform so well for other domains, such as an eccentric ellipse. We therefore consider the MFS-SVD approach in elliptic coordinates with Mathieu functions as basis functions for the latter. We illustrate the feasibility of the approach by numerical examples in both cases.

2024Journal article

Embargoed access

The MFS-SVD method for the laplace equation in three dimensions

Publication . Antunes, Pedro; Santos, Vinicius; Serranho, Pedro

The method of fundamental solutions (MFS) has been widely used to numerically solve boundary value problems involving linear partial differential equations. This method is easy to implement computationally and can be very effective for smooth domains and boundary conditions. The main drawback of the MFS is the ill-conditioning of the associated matrices, which may deteriorate the method’s accuracy. We present three methods to reduce the ill-conditioning of the classical MFS for the Laplace equation defined in bounded star-shaped domains in 3D. The idea is to expand the MFS basis functions in terms of spherical harmonics, in order to use the reduced QR factorization and singular value decomposition to deal with the ill-conditioning, leading to a better function basis that spans the same approximation space as the classical MFS. The numerical results illustrate that these approaches significantly decrease the ill-conditioning, allowing higher accuracy when compared to the classical MFS.

2025-02-12Journal article

Open access

A hybrid method for the time-harmonic inverse acoustic transmission problem

Publication . Paixão, João; Serranho, Pedro

The inverse transmission problem of scattering an acoustic wave by a penetrable object has several applications in various fields such as radar, sonar, geophysical exploration, medical imaging and non destructive testing. Here we propose a numerical hybrid method to inverse acoustic scattering by penetrable obstacles from far-field data in two-dimensions, that extends an iterative decomposition method to the transmission problem. The proposed method starts by reconstructing the scattered and interior field by imposing the far-field equation and one of the transmission conditions and, in the second step it uses the second transmission condition to update the position of the approximated boundary, by linearization. Also, we compared two approaches for the linearization step: a Newtontype method; and a gradient-type method with a penalty term for high oscillations of the solution. We also support the methods by a convergence result for a related optimization problem. Numerical results from eight incident directions show the method is feasible, though sensitive to noise.

2025-04-01Article

Open access