# UFed-GAN: A Secure Federated Learning Framework with Constrained Computation
and Unlabeled Data

Achintha Wijesinghe, Songyang Zhang, , Siyu Qi and Zhi Ding A. Wijesinghe, S.
Qi, and Z. Ding are with the Department of Electrical and Computer
Engineering, University of California, Davis, CA, 95616. (E-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>and zding@ucdavis.edu). S. Zhang
was with the University of California at Davis, Davis, CA, 95616 and now is
with the Department of Electrical and Computer Engineering, University of
Louisiana at Lafayette, Lafayette, LA 70504 (E-mail:
songyang.zhang@louisiana.edu).

###### Abstract

To satisfy the broad applications and insatiable hunger for deploying low
latency multimedia data classification and data privacy in a cloud-based
setting, federated learning (FL) has emerged as an important learning
paradigm. For the practical cases involving limited computational power and
only unlabeled data in many wireless communications applications, this work
investigates FL paradigm in a resource-constrained and label-missing
environment. Specifically, we propose a novel framework of UFed-GAN:
Unsupervised Federated Generative Adversarial Network, which can capture user-
side data distribution without local classification training. We also analyze
the convergence and privacy of the proposed UFed-GAN. Our experimental results
demonstrate the strong potential of UFed-GAN in addressing limited
computational resources and unlabeled data while preserving privacy.

###### Index Terms:

Federated learning, unlabeled data, data privacy, generative adversarial
networks.

##  I Introduction

The burgeoning rise of deep learning has shown remarkable achievements in
learning, based on the often voluminous amounts of data for centralized
training. However, in many cases of learning-based wireless connections for
collaboration, decentralized learning is vital to handle the heterogeneous
data distribution among nodes (users). Importantly, privacy concerns and
resource limitations also prevent direct data sharing. To ensure data privacy
and communication efficiency, federated learning (FL) [1] has emerged as an
important framework to disengage data collection and model training via local
computation and global model aggregation.

Despite reported successes, existing FL frameworks have certain limitations.
One major obstacle of FL in practice is the heterogeneity of data distribution
among participating FL users. It is known [2] that the accuracy of classic FL
frameworks such as FedAvg [1] could drop by 55% for some datasets showing non-
IID, i.e., not identically and independently distributed, data distributions.
To combat performance loss against non-IID datasets, the more general approach
of FedProx [3] may depend on certain unrealistic dissimilarity assumptions of
local functions [4]. Alternatively, generative adversarial network (GAN) [5]
provides another approach to address data heterogeneity. In GAN-based FL, GAN
models are used as a proxy to share user updates without training the global
model on the user side. For example, in [6], a global classifier is trained
using a user-shared generator of the user-end-trained conditional GANs
(cGANs). Another example is [7], the authors proposed to share the full user-
end GAN for generating a synthetic dataset. However, the high communication
cost and the potential privacy leakage hinder the performance gain of these
known GAN-based FL frameworks as discussed in [8]. Moreover, the training of
the entire GAN and other learning models sometimes can be impractical at the
user end, especially for nodes with limited computation resources, such as
computation-constrained sensors and devices [9]. How to develop a more
efficient GAN-sharing strategy to preserve privacy and handle limited
computation remains an open question in generative FL.

In addition to data heterogeneity and limited computation resources, most of
the existing works focus on supervised FL, where the performance depends
heavily on the availability of labeled training data. In practical
applications such as user clustering and video segmentation [10], the
computational and privacy limitations may prevent user-side data labeling.
Therefore, learning from unlabeled data is equally important for FL to reach
its full potential. Presently, only limited research works have specifically
addressed FL with unlabeled data, primarily due to inherent challenges. A
typical category of FL dealing with unlabeled data [11, 12] focuses on
clustering tasks, which may limit its generalization to other deep learning
tasks. Another line of FL focuses on unsupervised representation learning
[13], where knowledge distillation and contrast learning are applied to
address heterogeneous user data distributions. Other FL works on unlabeled
data [14, 15, 16] leverage the efficiency of latent space and may lack a
general description of the original data. As aforementioned, GAN-based
approaches can be intuitive solutions to capture the data distributions and
assist further applications, even without annotated labels.

In this work, we develop a novel FL framework, the Unsupervised Federated
Generative Adversarial Network (UFed-GAN), for resource-limited distributed
users without labeled data. The novelty is an innovative GAN-based FL and
data-sharing strategy to significantly reduce the computational cost at the
user end and to preserve privacy. Note that, instead of focusing on one
specific unsupervised learning task, we provide a general FL scheme to learn
the data distributions without labels. Our framework can be easily adapted to
handle specific learning tasks, including unsupervised representation
learning, user clustering, and semi-supervised classification.

Our contributions can be summarized as follows:

  * •

We propose a novel UFed-GAN as an FL framework to learn and characterize the
non-IID user data distributions from unlabeled user data. Our UFed-GAN
captures the underlying user data distributions without explicitly training a
local GAN model for each user, thereby significantly lowering the
computational cost on the user side. To our best knowledge, this is the first
work to address such constrained computation in GAN-based FL.

  * •

We analyze the convergence of UFed-GAN and prove that privacy leakage can be
prevented by our UFed-GAN, in comparison to traditional GAN-based FL.

  * •

Our experimental results in several benchmark datasets demonstrate the
performance of UFed-GAN in a semi-supervised classification setup.

In terms of organization, we first introduce the architecture of UFed-GAN and
a training strategy in Section II. Following the study on model convergence
and the privacy analysis in Section III. We present the experimental results
of UFed-GAN on several well-known datasets in Section IV. We provide
concluding remarks in Section V.

##  II Method and Architecture

###  II-A Problem Setup

Figure 1: UFed-GAN in a distributed learning setup in an untrustworthy
communication scenario, where users are assumed with less computational power.
An attacker may eavesdrop to understand the user data.

As a typical example of a resource-limited FL setup in Fig. 1, a server aims
to learn from user nodes, each with limited computational resources whereas
attackers may attempt to eavesdrop on the network links. Users may not be able
to annotate their raw data. Moreover, since the target tasks may be different
among users and the data may also be skewed, a non-IID data distribution shall
be considered in this scenario. Different from local users, the server has
sufficient computational resources to obtain a model that learns a global data
distribution from all the local data, without initial training data. Such a
setup is applicable in many distributed learning scenarios. For example, a
distributed camera/sensor system placed for object detection can benefit from
the collaboration of different cameras for better feature extraction, where
each digital camera or sensor may have limited computation power.

To demonstrate the privacy protection offered by UFed-GAN, we consider an
attacker that has access to the vulnerable communication links between
distributed users and the central server. Such attacks try to gain users’ data
features based on the information shared through the channels.

Note that, we aim to develop a novel data/model-sharing strategy for FL. The
strategy could handle unlabeled data and capture user data distributions in
the scenario with limited local computation resources. The proposed framework
should offer flexible integration with various unsupervised and semi-
supervised learning tasks, such as latent representation learning, user
clustering, and semi-supervised classification [13].

###  II-B UFed-GAN

Figure 2:  Communication rounds till the convergence of UFed-GAN. We use the
inception score (IS) as the measure of convergence.

We now explain the framework and training process of UFed-GAN, which allows
private and secure learning from unlabeled data in a distributed learning
setup. Our proposed UFed-GAN aims to train a GAN model on the server to
capture the underlying user data distributions without implementing complex
GAN training on the user side.

First, for each user $u$, we initiate a GAN model on the server, including a
generator ($G_{u}$) and a discriminator ($D_{u}$). Due to label
inaccessibility, we select deep convolutional GANs (DCGANs) [17] as the
backbone. The details of choices for GAN architecture will be elaborated in
Section II-D.

The GAN training comes in three steps, which contains two steps of $D$
training and one step of $G$ training. We split the dual-step $D$ training
into the server side and the user side. On one side, the server initiates a
discriminator $D_{u}$ and then shares the initiated model with the
corresponding user $u$. Subsequently, on the other end, the user performs a
forward pass (FP) on $D_{u}$ using a single batch of real local data $I_{u}$.
The gradients and loss are calculated and then shared with the server.
Compared with training a full GAN on the user side, this step can
significantly reduce the computational cost and be easily deployed in
computation-constrained devices. Upon receiving the updated information of
$D_{u}$ from the user $u$, the server completes the training of $D_{u}$. It
generates a noise vector z to pass through $G_{u}$. Finally, synthetic data
$G_{u}(\textbf{z})$ is generated from the generator. $G_{u}(\textbf{z})$ is
then sent to $D_{u}$ to calculate the corresponding gradients and loss. These
received gradient updates are combined with the gradient updates of the
previous step and then back-propagated through $D_{u}$ to update the
parameters.

Similar to conventional GAN training, starting with a noise vector z’, we
train $G_{u}$ with forward- and backward-propagation to update its parameters.
In each communication round, the above process repeats until GAN convergence
to a favorable point. We illustrate this training process further in Fig. 2.
For model convergence monitoring and the stopping criterion, we use inception
score (IS) [18], which measures the characteristics of the generated images.
After convergence, we create a synthetic dataset using the trained $D_{u}$.
With the generated synthetic dataset, we can design corresponding unsupervised
or semi-supervised algorithms to implement specific learning tasks. For
example, in a semi-supervised classification task, we could apply the MoCo
[19], which uses dictionary lookups in contrastive learning to obtain the
global classifier. The pseudocode of the proposed training strategy is
presented in Algorithm 1.

Algorithm 1 UFed-GAN: Training Algorithm

for each user $u$ do

Server initialization of $G_{u}$ and $D_{u}$

end for

for each communication round $r$, until the GAN convergence do

for each step $t$ do

Share $D_{u}$ with user $u$.

Perform FP in $D_{u}$ with user data $\mathcal{I}_{u}$ and share the gradient
updates $\nabla W_{u}$.

Perform FP in $D_{u}$ with fake data $G(z_{t})$ where $z_{t}$ is a random
noise vector and get the gradient updates $\nabla W_{z}$.

Update $D_{u}$ with ($\nabla W_{u}+\nabla W_{z}$).

Train $G_{u}$ with trained $D_{u}$ and random noise vectors.

end for

Generate an unlabeled dataset using each $G_{u}$.

end for

###  II-C Attacker Model

We now introduce the attacker model to quantify the privacy leakage of UFed-
GAN. It is highly challenging, if not impossible, to obtain access to the
global generator $G$ given a secure server or to guess the exact architecture
of $G$, regardless of the computation prowess of the attacker. Therefore, as
suggested in [8], we focus on a reconstruction attack [20] in this work, where
an attacker attempts to reconstruct the training data. Let $\theta$ be the
parameters released to the communication channel by the user. We denote the
releasing mechanism by $\mathcal{M}$ and the information that an attacker
$\mathcal{A}$ could obtain by $\mathcal{M}(\theta)$. According to the UFed-GAN
framework, $\mathcal{M}(\theta)$ is the discriminator gradients and the loss
values. Let $\mathcal{I}$ represent the reconstructed data, we have

$\mathcal{A}:\mathcal{M}(\theta)\mapsto\mathcal{I}.$ (1)

Suppose that the generator $G_{\mathcal{A}}$ of attacker $\mathcal{A}$ has the
same architecture as $G$ but with initial weights $W_{\mathcal{A}}$ different
from those of $G$, represented by $W_{G}$. In parallel to the server training,
we train $G_{\mathcal{A}}$ at the attacker’s end.

###  II-D GAN Architecture

Due to label inaccessibility and resource constraints, we adopt the
unsupervised DCGANs [17] over cGANs [8] which saves extra computation needs
for any pseudo-labeling. The generator architecture follows five transposed
convolutional layers. The first layer takes an input with 100 channels and
maps it to 1024 channels. Every subsequent layer reduces the number of
channels by half. Every layer uses ReLU activation except for the Tanh
activation for the final layer. All the layers in both the generator and the
discriminator use $4\times 4$ kernels and batch normalization for each layer
before the final layer. For the discriminator model, we use four convolutional
layers. The first layer accepts similar channel sizes of the data samples and
maps to 256 channels. Every subsequent layer doubles the number of channels
except the final layer, which outputs a single channel. The final layer uses a
Sigmoid activation whereas all other layers use LeakyReLU activation.

##  III Convergece and Privacy Analysis of UFed-GAN

In this section, we present the convergence and privacy analysis of the
proposed UFed-GAN. We introduce the major proof steps and refer those
interested to our corresponding references for more details.

###  III-A Convergence of the discriminator

Let $\mathcal{G}$ and $\mathcal{D}$ be the generator and the discriminator of
a GAN, respectively. Assume $\mathcal{G}$ is capable of capturing a
distribution $p_{GS}$ on the server and we are interested in learning a user
distribution $p_{data}(x)$.

Proposition 1. Any $\mathcal{D}$ initiated on a server and trained in
accordance to Algorithm 1 with $\mathcal{G}$ and $p_{data}(x)$ converges to a
unique $\mathcal{D}^{*}$ for the given $\mathcal{G}$ as presented in [5],
i.e.,

$\mathcal{D}^{*}=\frac{p_{data(x)}}{p_{data(x)}+p_{GS}}$ (2)

Since UFed-GAN merely splits the GAN training, the proof of Proposition 1
shall directly follow that in [5]. This proposition serves as a guarantee of
the convergence of the server-side discriminator. It shows that the
discriminator is still capable of capturing the user side’s data distribution.
This helps the generator on the server-side to generate user-like data as
illustrated in the following proposition.

###  III-B Convergence of the generator

Proposition 2. Any $\mathcal{G}$ initiated on a server and trained in
accordance to Algorithm 1 with $\mathcal{D}$ and $p_{data}(x)$ converges to a
unique $\mathcal{G}^{*}$ which captures $p_{data}(x)$. i.e.
$p_{GS}=p_{data}(x)$.

Since UFed-GAN does not alter the training of $\mathcal{G}$, we can imitate
and adopt the proof steps in [5]. Proposition 2 suggests that the server-side
generator converges to the same generator that could have been trained
locally. Therefore, on the server, we are able to regenerate synthetic samples
which resemble the user data in terms of data distribution.

###  III-C Divergence of any discriminator other than $\mathcal{G}$

Proposition 3. Any generator $G$, other than $\mathcal{G}$ trained in
accordance to the Algorithm 1 with $\mathcal{D}$ diverges from unique
$\mathcal{G}^{*}$. i.e. $p_{GS}\neq p_{data}(x)$.

To prove Proposition 3, we adopt a similar proof process as provided in [8].
Following Proposition 1 and Proposition 2, the pair of $\mathcal{G}$ and
$\mathcal{D}$ is unique. Therefore, at each training step
$\mathcal{G}^{{}^{\prime}}=G^{{}^{\prime}}$ must be asserted. Hence, any $G$
difference from $\mathcal{G}$ at any step fails to capture $p_{data}(x)$.

##  IV Results and Discussion

In this section, we present the experimental results on both utility and
privacy.

###  IV-A Evaluation of the Utility

In a common semi-supervised setting as [13], let $N$ be the number of users,
$\beta$ be the concentration parameter of Dirichlet distribution
($Dir_{N}(\beta)$), and $s_{ij}$ be a sample taken from $Dir_{N}(\beta)$. We
assign $s_{ij}$ in proportion to the $i$-th class size of the user $j$. We
pick $N=10$ and $\beta=0.5$ in accordance with [13]. All model comparisons are
based on the linear evaluation protocol, which trains a linear classifier on
top of representations or regenerated fake data [21].

TABLE I: Classification accuracy comparison of different FL approaches over three datasets. Part of the results in this table are reported from [13]. Method | CIFAR 10 | SVHN | FashionMNIST
---|---|---|---
FedSimCLR | 52.88 | 76.50 | 79.44
\+ FedX | 57.95 | 77.70 | 82.47
FedMoCo | 57.82 | 70.99 | 83.58
\+ FedX | 59.43 | 73.92 | 84.65
FedBYOL | 53.14 | 67.32 | 82.37
\+ FedX | 57.79 | 69.05 | 84.30
FedProtoCL | 52.12 | 50.19 | 83.57
\+ FedX | 56.76 | 69.75 | 83.34
FedU | 50.79 | 66.22 | 82.03
\+ FedX | 57.26 | 68.39 | 84.12
Full GAN | 68.77 | 80.17 | 86.25
UFed-GAN | 67.0 | 80.109 | 86.33

We consider three well-known datasets: CIFAR10 [22], SVHN [23] and
FashionMNIST [24]. Comparative results against five other FL algorithms are
presented in Table I. These algorithms are: FedSimCLR [25], FedMoco [19],
FedBYOL [26], FedProtoCL [27] and FedU [28]. For each method, we present their
accuracy on the respective dataset, together with their accuracy when further
applying FedX [13]. We also compare the results with “full GAN” sharing.

From the results, UFed-GAN outperforms all other FL methods in the benchmark
group, with an improvement of around 8% in CIFAR10, 3% in SVHN, and 2% in
FashionMNIST. The accuracy gain arises from the power of GANs to understand
the underlying data distribution of users and to generate synthetic data by
preserving essential features. Another observation is that UFed-GAN is
dataset-agnostic in terms of performance, delivering the best outputs in all
tested datasets. This observation promotes the generalizability of the
proposed method. In fact, UFed-GAN achieves similar performance as with full
GAN sharing. However, full GAN sharing is prone to severe privacy leakage as
shown in [8] and additionally requires heavy computation at each user node,
which is in conflict with the FL objective of privacy preservation and
conserving computation resources for users.

###  IV-B Evaluation of Privacy

We now evaluate the privacy leakage of the proposed UFed-GAN with respect to
the attacker $\mathcal{A}$ as described in Section II-C. Suppose that
$\mathcal{A}$ has access to each communication round. We initialize the
generator of $\mathcal{A}$ as $G_{\mathcal{A}}$, with some random weights and
eavesdrop on user uplink and access $\mathcal{M}(\theta)$. $\mathcal{A}$
trains $G_{\mathcal{A}}$ similarly as with the server-side training. The
design of $G_{\mathcal{A}}$ is constrained by two parameters, the exact
generator architecture and the initial weights $W_{G}$ of the generator at the
server. Therefore, any attacker selecting the accurate generator architecture
and initial weights is practically unachievable. However, in our experiments,
we assume $\mathcal{A}$ knows the exact architecture of $G$, but with
different random initial weights $W_{\mathcal{A}}\neq W_{G}$. We compare the
generated images of the $G$ and $G_{\mathcal{A}}$ trained on the FashionMNIST
dataset in Fig. 3. It can be clearly seen that the generator $G$ on the cloud
server captures the user’s underlying data distribution, whereas
$G_{\mathcal{A}}$ converges to a trivial point. Moreover, almost no useful
visualization information is gained by the attacker as shown in Fig. 3. The
main reason is the uniqueness of the generator and the discriminator pair as
presented in Proposition 1.

(a)

(b)

Figure 3: Generated images from (a) cloud-server’s model. (b) attacker’s model. TABLE II: FID score, IS score, and SSIM of the $\mathcal{A}$ and the cloud server after 100 communication rounds on the FashionMNIST dataset. Metric | Attaker | Cloud Server
---|---|---
FID | 566.83 | 172.06
IS | 1.01 | 3.15
SSIM | 0.0067 | 0.8191

To examine privacy leakage quantitatively, we use the Frechet Inception
Distance (FID) score [29], IS, and structural similarity index measure (SSIM)
[30]. As discussed in the paper [31], the similarity between the generated
images and real data quantifies the privacy leakage. In table IV-B, we record
average FID, IS, and SSIM scores for the data generated by $\mathcal{A}$ and
the cloud server. Lower FID values, higher SSIM, and larger IS values
represent better reconstruction quality. The FID score for $\mathcal{A}$ is
higher than the cloud server by a great margin. This shows that, compared to
the cloud server, $\mathcal{A}$ generated data carries less information about
the training data. We further corroborate this observation by comparing the
SSIM and IS values as well. The experimental results demonstrate the privacy
preservation of UFed-GAN against full-GAN sharing.

##  V Conclusion

In this work, we develop a novel framework of UFed-GAN to address the
challenges imposed by the lack of labeled data and by limited local
computation resources in federated learning. Moreover, we propose a separate
training strategy and a sharing scheme based on DCGANs. We provide an analysis
of the convergence and privacy leakage of the proposed framework. Our
empirical results demonstrate the superior performance of UFed-GAN in
comparison against benchmark FL methods. We plan to investigate the
communication overhead reduction for GAN-based FL and the application of
semantic learning in distributed learning in future works.

## References

  * [1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ , Lauderdale, FL, USA, Apr. 2017, pp. 1273–1282.
  * [2] Y. Zhao, M. Li, L. Lai, N. Suda, D. Civin, and V. Chandra, “Federated learning with non-iid data,” _arXiv preprint arXiv:1806.00582_ , 2018.
  * [3] T. Li, A. K. Sahu, M. Sanjabi, M. Zaheer, A. Talwalkar, and V. Smith, “On the convergence of federated optimization in heterogeneous networks,” _arXiv preprint arXiv:1812.06127_ , 2018.
  * [4] X. Yuan and P. Li, “On convergence of fedprox: Local dissimilarity invariant bounds, non-smoothness and beyond,” in _Advances in Neural Information Processing Systems_ , New Orleans, LA, USA, Jul. 2022, pp. 10 752–10 765.
  * [5] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial nets,” in _Advances in Neural Information Processing Systems_ , vol. 27, Montreal, Canada, Dec. 2014.
  * [6] H. Zhang, Z. Zhang, A. Odena, and H. Lee, “Consistency regularization for generative adversarial networks,” in _International Conference on Learning Representations_ , Addis Ababa, Ethiopia, Apr. 2020.
  * [7] X. Cao, G. Sun, H. Yu, and M. Guizani, “Perfed-gan: personalized federated learning via generative adversarial networks,” _IEEE Internet of Things Journal_ , vol. 10, no. 5, pp. 3749–3762, Mar. 2023.
  * [8] A. Wijesinghe, S. Zhang, and Z. Ding, “Ps-fedgan: an efficient federated learning framework based on partially shared generative adversarial networks for data privacy,” _arXiv preprint arXiv:2305.11437_ , 2023.
  * [9] J. Mu, D. Xie, H. Huang, and X. Jing, “Computation-constrained spectrum sensing in iot-based scenarios,” _IET Communications_ , vol. 14, no. 20, pp. 3631–3638, Nov. 2020.
  * [10] J. Bekker and J. Davis, “Learning from positive and unlabeled data: a survey,” _Machine Learning_ , vol. 109, pp. 719–760, Apr. 2020.
  * [11] D. K. Dennis, T. Li, and V. Smith, “Heterogeneity for the win: One-shot federated clustering,” in _Proceedings of the 38th International Conference on Machine Learning_ , Jul. 2021, pp. 2611–2620.
  * [12] A. Ghosh, J. Chung, D. Yin, and K. Ramchandran, “An efficient framework for clustered federated learning,” in _Advances in Neural Information Processing Systems_ , Dec. 2020, pp. 19 586–19 597.
  * [13] S. Han, S. Park, F. Wu, S. Kim, C. Wu, X. Xie, and M. Cha, “Fedx: Unsupervised federated learning with cross knowledge distillation,” in _European Conference on Computer Vision_ , Tel Aviv, Israel, Nov. 2022, pp. 691–707.
  * [14] M. Servetnyk, C. C. Fung, and Z. Han, “Unsupervised federated learning for unbalanced data,” in _GLOBECOM 2020 - 2020 IEEE Global Communications Conference_ , Taipei, Taiwan, Dec. 2020, pp. 1–6.
  * [15] N. Lu, Z. Wang, X. Li, G. Niu, Q. Dou, and M. Sugiyama, “Federated learning from only unlabeled data with class-conditional-sharing clients,” in _International Conference on Learning Representations_ , Apr. 2022.
  * [16] E. S. Lubana, C. I. Tang, F. Kawsar, R. P. Dick, and A. Mathur, “Orchestra: unsupervised federated learning via globally consistent clustering,” _arXiv preprint arXiv:2205.11506_ , 2022.
  * [17] A. Radford, L. Metz, and S. Chintala, “Unsupervised representation learning with deep convolutional generative adversarial networks,” _arXiv preprint arXiv:1511.06434_ , 2015.
  * [18] T. Salimans, I. Goodfellow, W. Zaremba, V. Cheung, A. Radford, and X. Chen, “Improved techniques for training gans,” in _Advances in neural information processing systems_ , Barcelona, Spain, Dec. 2016.
  * [19] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick, “Momentum contrast for unsupervised visual representation learning,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , Jun. 2020, pp. 9729–9738.
  * [20] J. Hayes, L. Melis, G. Danezis, and E. De Cristofaro, “Logan: evaluating privacy leakage of generative models using generative adversarial networks,” _arXiv preprint arXiv:1705.07663_ , pp. 506–519, 2017.
  * [21] F. Zhang, K. Kuang, Z. You, T. Shen, J. Xiao, Y. Zhang, C. Wu, Y. Zhuang, and X. Li, “Federated unsupervised representation learning,” _arXiv preprint arXiv:2010.08982_ , 2020.
  * [22] A. Krizhevsky, “Learning multiple layers of features from tiny images,” pp. 32–33, 2009. [Online]. Available: https://www.cs.toronto.edu/~kriz/learning-features-2009-TR.pdf
  * [23] Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng, “Reading digits in natural images with unsupervised feature learning,” in _NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011_ , Granada, Spain, Dec. 2011.
  * [24] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” _arXiv preprint arXiv:1708.07747_ , 2017.
  * [25] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton, “A simple framework for contrastive learning of visual representations,” in _Proceedings of the 37th International Conference on Machine Learning_ , vol. 119, Vienna, Austria, Jul. 2020, pp. 1597–1607.
  * [26] J.-B. Grill, F. Strub, F. Altché, C. Tallec, P. Richemond, E. Buchatskaya, C. Doersch, B. Avila Pires, Z. Guo, M. Gheshlaghi Azar _et al._ , “Bootstrap your own latent-a new approach to self-supervised learning,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 21 271–21 284, Dec. 2020.
  * [27] J. Li, P. Zhou, C. Xiong, and S. C. Hoi, “Prototypical contrastive learning of unsupervised representations,” _arXiv preprint arXiv:2005.04966_ , 2020.
  * [28] W. Zhuang, X. Gan, Y. Wen, S. Zhang, and S. Yi, “Collaborative unsupervised visual representation learning from decentralized data,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , Oct. 2021, pp. 4912–4921.
  * [29] M. Heusel, H. Ramsauer, T. Unterthiner, B. Nessler, and S. Hochreiter, “Gans trained by a two time-scale update rule converge to a local nash equilibrium,” in _Advances in Neural Information Processing Systems_ , vol. 30, Long Beach, CA, USA, Dec. 2017.
  * [30] Z. Wang, A. Bovik, H. Sheikh, and E. Simoncelli, “Image quality assessment: from error visibility to structural similarity,” _IEEE Transactions on Image Processing_ , vol. 13, no. 4, pp. 600–612, 2004.
  * [31] D. Dangwal, V. T. Lee, H. J. Kim, T. Shen, M. Cowan, R. Shah, C. Trippel, B. Reagen, T. Sherwood, V. Balntas _et al._ , “Analysis and mitigations of reverse engineering attacks on local feature descriptors,” _arXiv preprint arXiv:2105.03812_ , 2021.


Choice Disjunctive Queries in Logic Programming

Keehang Kwon
Dept. of Computer Engineering, DongA University

Busan 604-714, Korea

<EMAIL_ADDRESS>
Abstract: One of the long-standing research problems on logic programming is
to treat the cut predicate in a logical, high-level way. We argue that this
problem can be solved by adopting linear logic and choice-disjunctive goal
formulas of the form $G_{0}\oplus G_{1}$ where $G_{0},G_{1}$ are goals. These
goals have the following intended semantics: $choose$ the true disjunct
$G_{i}$ and execute $G_{i}$ where $i(=0\ {\rm or}\ 1)$, while $discarding$ the
unchosen disjunct. Note that only one goal can remain alive during execution.
These goals thus allow us to specify mutually exclusive tasks in a high-level
way.

keywords: Prolog, mutual exclusion, cut, linear logic, computability logic

##  1 Introduction

One of the long-standing research problems on logic programming is to treat
the extra-logical primitive in a high-level way. The advances of logic
programming have enriched Horn clauses with additional programming primitives
in a high-level way (higher-order programming, modules, local constants, etc).
Nevertheless some key constructs could not be dealt with in a high-level way,
in particular when we are concerned with mutual exclusion (and the cut
predicate).

Consequently, much attention [10, 11, 6] has been given to finding a semantics
that captures the cut predicate. However, these proposals are not $logical$ in
that a well-defined yet simple declarative meaning as well as its proof theory
are still missing, exposing low-level operational details.

In this paper, inspired by the work in [4], we propose a purely logical
solution to this problem. It involves the direct employment of linear logic
[2] to allow for choice-disjunctive goals. A choice-disjunctive goal is of the
form $G_{0}\oplus G_{1}$ where $G_{0},G_{1}$ are goals. (A more intuitive name
would be $choose(G_{0},G_{1})$.) Executing this goal with respect to a program
$D$ – $ex(D,G_{0}\oplus G_{1})$ – has the following intended semantics:

$\mbox{\rm choose a true one between}\ ex(D,G_{0}),ex(D,G_{1}).$

An illustration of this aspect is provided by the following definition of the
relation $son(X,Y)$ which holds if $Y$ is a son of $X$.:

$son(X,Y)$ ${\rm:-}$ |  $(male(X)\land father(Y,X))\ \oplus$
---|---
|  $(female(X)\land mother(Y,X)).$

The body of the definition above contains a mutually exclusive goal, denoted
by $\oplus$. As a particular example, solving the query $son(tom,Y)$ would
result in selecting and executing the first goal $male(tom)\land
father(tom,Y)$, while discarding the second one. The given goal will succeed,
producing solutions for $Y$. Of course, we can specify mutually exclusive
goals using cut in Prolog, but it is well-known that cuts complicates the
declarative meaning of the program [1]. Our language makes it possible to
formulate mutually exclusive goals in a high-level way. The class of choice
disjunctive goals is, in a sense, a high-level abstraction for the cut
predicate.

As seen from the example above, choice-disjunctive goals can be used to
perform mutually exclusive tasks. There are several linear logic languages [3,
12] in which goals of the form $G_{0}\oplus G_{1}$ are present. A common yet
problematic aspect of these works is their treatment of the $\oplus$-goals:
these goals are treated as inclusive-OR (or classical disjunctive) goals
rather than exclusive-OR ones:

$ex(D,G_{0}\oplus G_{1})\ {\rm if}\ ex(D,G_{0})\ \lor ex(D,G_{1})$

where $\lor$ represents classical disjunction. Hence, the declarative reading
of $\oplus$ – known as the machine’s choice – is $violated$ in these
languages.

A satisfactory solution can be obtained by adding the choice action, as
discussed above, to their execution model of $\oplus$ so that the execution
respects the declarative reading of $\oplus$, while maintaining provability.
Hence, the main difference is that, once a goal is chosen, the unchosen goal
will be discarded in our language, while it will remain alive (typically
through a creation of a choicepoint) in those languages.

This paper proposes Prolog⊕, an extension of Prolog with choice-disjunctive
operators in goal formulas. The remainder of this paper is structured as
follows. We describe Prolog⊕ in the next section. In Section 3, we present
some examples of Prolog⊕. Section 4 concludes the paper.

##  2 The Language

The language is a version of Horn clauses with choice-disjunctive goals. Note
that we disallow linear clauses here, thus allowing only reusable clauses. It
is described by $G$\- and $D$-formulas given by the syntax rules below:

|  $G::=$ |  $A\;|\;t=s\;|\;G\land G\;|\;\exists x\ G\;|\;G\oplus G$
---|---|---
|  $D::=$ | $A\;|\;G\supset A\ \;|\;\forall x\ D\;|\;D\land D$

In the rules above, $t,s$ represent terms, and $A$ represents an atomic
formula. A $D$-formula is called a Horn clause with choice-disjunctive goals.

The logic programming paradigm such as Prolog was originally founded on the
resolution method. But this approach was difficult to extend to richer logics.
The use of sequent calculus allows us to overcome this limit. Furthermore,
uniform proofs [9] allows us to execute logic programs in an efficient way by
integrating two separate phases – the proof phase and the execution phase –
into a single phase. We adopt this approach below.

We will present a machine’s strategy for this language as a set of rules.
These rules in fact depend on the top-level constructor in the expression, a
property known as uniform provability[8, 9, 7]. Note that execution alternates
between two phases: the goal-reduction phase and the backchaining phase. In
the goal-reduction phase (denoted by $ex(D,G)$), the machine tries to solve a
goal $G$ from a clause $D$ by simplifying $G$ . The rule (6) – (9) are related
to this phase. If $G$ becomes an atom, the machine switches to the
backchaining mode. This is encoded in the rule (5). In the backchaining mode
(denoted by $bc(D_{1},D,A)$), the machine tries to solve an atomic goal $A$ by
first reducing a Horn clause $D_{1}$ to simpler forms (via rule (3) and (4))
and then backchaining on the resulting clause (via rule (1) and (2)).

Definition 1.  Let $G$ be a goal and let $D$ be a program. Then the notion of
executing $\langle D,G\rangle$ – $ex(D,G)$ – is defined as follows:

  * (1)

$bc(A,D,A)$. % This is a success.

  * (2)

$bc((G_{0}\supset A),D,A)$ if $ex(D,G_{0})$.

  * (3)

$bc(D_{1}\land D_{2},D,A)$ if $bc(D_{1},D,A)$ or $bc(D_{2},D,A)$.

  * (4)

$bc(\forall xD_{1},D,A)$ if $bc([t/x]D_{1},D,A)$.

  * (5)

$ex(D,A)$ if $bc(D,D,A)$.

  * (6)

$ex(D,t=s)$ if $unify(t,s)$ % $t,s$ are terms.

  * (7)

$ex(D,G_{0}\land G_{1})$ if $ex(D,G_{0})$ $and$ $ex(D,G_{1})$.

  * (8)

$ex(D,\exists xG_{0})$ if $ex(D,[t/x]G_{0})$.

  * (9)

$ex(D,G_{0}\oplus G_{1})$ if select a successful disjunct between
$ex(D,G_{0})$ and $ex(D,G_{1})$. % This goal behaves as exclusive-OR.

In the above rules, only the rule (9) is a novel feature. To be specific, this
goal first attempts to execute $G_{0}$, discarding $G_{1}$. If it succeeds,
then do nothing (and do not leave any choice point for $G_{1}$ ). If it fails,
then $G_{1}$ is attempted.

Implementing $G_{0}\oplus G_{1}$ poses no difficulties. For example, it can be
done by translating it to a Prolog disjunctive goal of the form
$(G_{0},!);G_{1}$ where ; denotes a Prolog disjuction. The cut then destroys
the choice point created for $G_{1}$ if $G_{0}$ succeeds. On the contrary, the
same goal $G_{0}\oplus G_{1}$ will be translated to $G_{0};G_{1}$ in other
linear logic languages.

The following theorem connects our language to linear logic. Its proof is
obtained from [3] and from the simple observation that our modified execution
rule preserves provability.

###### Theorem 1

Let $D$ be a program and let $G$ be a goal. Then, $ex(D,G)$ terminates with a
success if and only if $G$ follows from $D$ in intuitionistic linear logic.
Furthermore, it respects the declarative reading of the operator $\oplus$.

##  3 Examples

Let us first consider the relation $f(X,Y)$ specified by two rules:

  * (1)

if $X<2$, then $Y=0$.

  * (2)

if $X\geq 2$, then $Y=3$.

The two conditions are mutually exclusive which is expressed by using the cut
in traditional logic programming as shown below:

$f(X,0):-\ X<2,!.$ $f(X,3):-\ X\geq 2.$

Using cut, we can specify mutually exclusive goals, but cuts affect the
declarative meaning of the program. Our language makes it possible to
formulate mutually exclusive goals through the choice-disjunctive goals as
shown below:

$f(X,Y)$ ${\rm:-}$ |  $(X\geq 2\land Y=3)\ \oplus$
---|---
|  $(X<2\land Y=0)$

The new program, equipped with $\oplus$-goals, is more readable than the
original version with cuts, while preserving the same efficiency. A similar
example is provided by the following “max” program that finds the larger of
two numbers.

$max(X,Y,Max)$ ${\rm:-}$ |  $(X\geq Y\land Max=X)\ \oplus$
---|---
|  $(X<Y\land Max=Y)$

These two goals in the body of the above clause are mutually exclusive. Hence,
only one of these two goals can succeed. For example, consider a goal
$max(3,9,Max)$. Solving this goal has the effect of choosing and executing the
second goal $(3<9)\land Max=9$, producing the result $Max=9$.

As another example, we consider the relation $member(X,L)$ for establishing
whether $X$ is in the list $L$. A typical Prolog definition of $member(X,L)$
is shown below:

$member(X,[Y|L])$ ${\rm:-}$ |  $(Y=X)\ \lor member(X,L)$
---|---

This definition is nondeterministic in the sense that it can find any
occurrence of $X$. Our language in Section 2 makes it possible to change
$member$ to be deterministic and more efficient: only one occurrence can be
found. An example of this is provided by the following program.

$member(X,[Y|L])$ ${\rm:-}$ |  $(Y=X)\ \oplus member(X,L)$
---|---

As a final example, we consider the relation $rprime$ for establishing whether
the keyboard input data $X$ is prime or not. An example of this is provided by
the following program.

$rprime$ ${\rm:-}$ |  $read(X)\land$
---|---
|  $(prime(X)\land\ write(`prime^{\prime}))\oplus$
|  $(composite(X)\land\ write(`composite^{\prime}))$

##  4 Conclusion

In this paper, we have considered an extension to Prolog with choice-
disjunctive goals. This extension allows goals of the form $G_{0}\oplus G_{1}$
where $G_{0},G_{1}$ are goals. These goals are particularly useful for
replacing the cut in Prolog, making Prolog more concise and more readable.

In the near future, we plan to investigate the connection between Prolog⊕and
Japaridze’s Computability Logic(CL)[4, 5]. CL is a new semantic platform for
reinterpreting logic as a theory of tasks. Formulas in CL stand for
instructions that can carry out some tasks. We plan to investigate whether our
operational semantics is sound and complete with respect to the semantics of
CL.

## References

  * [1] I. Bratko, “Prolog:programming for AI ”, Addison Wesley, 2001 (3rd edition).
  * [2] J.Y. Girard, “Linear Logic”, Theoretical Computer Science, vol.50, pp.1–102, 1987\.
  * [3] J. Hodas and D. Miller, “Logic Programming in a Fragment of Intuitionistic Linear Logic”, Information and Computation, vol.110, pp.327–365, 1994.
  * [4] G. Japaridze, “Introduction to computability logic”, Annals of Pure and Applied Logic, vol.123, pp.1–99, 2003.
  * [5] G. Japaridze, “Sequential operators in computability logic”, Information and Computation, vol.206, No.12, pp.1443-1475, 2008.
  * [6] J. Kriener and A. King, “RedAlert: Determinacy Inference for Prolog”, Theory and Practice of Logic Programming, vol.11, no.4-5. pp.182–196.
  * [7] E. Komendantskaya and V. Komendantsky, “On uniform proof-theoretical operational semantics for logic programming”, In J.-Y. Beziau and A.Costa-Leite, editors, Perspectives on Universal Logic, pages 379–394. Polimetrica Publisher, 2007.
  * [8] D. Miller, “A logical analysis of modules in logic programming”, Journal of Logic Programming, vol.6, pp.79–108, 1989.
  * [9] D. Miller, G. Nadathur, F. Pfenning, and A. Scedrov, “Uniform proofs as a foundation for logic programming”, Annals of Pure and Applied Logic, vol.51, pp.125–157, 1991.
  * [10] A. Porto, “A structured alternative to Prolog with simple compositional semantics”, Theory and Practice of Logic Programming, vol.11, No.4-5, pp.611-627, 2011.
  * [11] A. Saurin, “Towards Ludics Programming: Interactive Proof Search”, International Conference on Logic Programming, pages 253–268. 2008.
  * [12] M. D. Winikoff, “Logic Programming with Linear Logic”, PhD. Thesis, Univ. Melbourne, 1997\.


# Spectral approach to Korteweg-de Vries equations on the compactified real
line

Christian Klein  Institut de Mathématiques de Bourgogne, UMR 5584
Université de Bourgogne-Franche-Comté, 9 avenue Alain Savary, 21078 Dijon
Cedex, France
E-mail<EMAIL_ADDRESS>and  Nikola Stoilov  Institut de
Mathématiques de Bourgogne, UMR 5584
Université de Bourgogne-Franche-Comté, 9 avenue Alain Savary, 21078 Dijon
Cedex, France
E-mail<EMAIL_ADDRESS>
###### Abstract.

We present a numerical approach for generalised Korteweg-de Vries (KdV)
equations on the real line. In the spatial dimension we compactify the real
line and apply a Chebyshev collocation method. The time integration is
performed with an implicit Runge-Kutta method of fourth order. Several
examples are discussed: initial data bounded but not vanishing at infinity as
well as data not satisfying the Faddeev condition, i.e. with a slow decay
towards infinity.

This work is partially supported by the ANR-FWF project ANuI -
ANR-17-CE40-0035, the isite BFC project NAANoD, the ANR-17-EURE-0002 EIPHI and
by the European Union Horizon 2020 research and innovation program under the
Marie Sklodowska-Curie RISE 2017 grant agreement no. 778010 IPaDEGAN

##  1\. Introduction

Generalised Korteweg-de Vries (gKdV) equations,

(1) $u_{t}(x,t)+u_{xxx}(x,t)+u(x,t)^{p-1}u_{x}(x,t)=0,$

where $p\in\mathbb{N}$, $u:\mathbb{R}\times\mathbb{R}^{+}\mapsto\mathbb{R}$,
appear as asymptotic models in hydrodynamics, nonlinear optics, plasma
physics, Bose-Einstein condensates, and essentially in most situations where
predominantly one-dimensional phenomena are discussed and where dispersion
dominates dissipation. Whereas this applies in particular to the case of the
classical Korteweg-de Vries (KdV) equation ($p=2$), there are applications for
instance in electrodynamics for the modified KdV equation ($p=3$), see [21].
Because of their importance in applications, there has been a considerable
activity in developing numerical approaches for the gKdV equations. For
initial data which are periodic or rapidly decreasing, numerical approaches
based on the approximation of $u$ in (1) via truncated Fourier series, i.e.,
trigonometric polynomials, are very efficient, see for instance [14, 15] and
references therein.

The Fourier approach, that is restricting the data to an interval
$L[-\pi,\pi]$ ($L=const$, $L\in\mathbb{R}^{+}$) and continuing them
periodically with period $2\pi L$ on the whole real line works very well for
periodic functions and exhibits _spectral convergence_ , namely an exponential
decrease of the numerical error with the number of Fourier modes. Schwartz
class functions can be treated as periodic as one works with a finite
precision and since $L$ can be chosen large enough such that all necessary
derivatives of $u$ vanish at the domain boundaries with numerical precision.
However, the same approach for initial data which do not tend to zero or are
only slowly decreasing to zero for $x\to\infty$, would in general imply a
Gibbs phenomenon at the domain boundaries. The resulting method would
therefore be only of first order in the number of Fourier modes, making it
impossible to reach the high resolution necessary to treat e.g. rapid
oscillations in the solution. Therefore, such situations are typically treated
on a finite interval. This leads to the problem of how to impose boundary
conditions, so that inside the computational domain the solution is the same
as if the computation was done on the whole real line. Such boundary
conditions are called _transparent_. Bérenger [2] introduced _perfectly
matched layers_ (PML) in electrodynamics to address this problem by extending
the computational domain to layers glued to the domain boundaries. Inside the
layers, the equation under consideration is deformed to a dissipative one,
which is chosen to efficiently dissipate the solution. Whereas this works well
for linear equations, examples for the nonlinear Schrödinger equation, see
[26, 3], showed that in a nonlinear setting there will be back reflections
from the layers to the computational domain. For integrable equations exact
transparent boundary conditions (TBC) can be given, e.g. for the case of
modified KdV see [27] based on [9]. The problem with both PML and TBC is that
they in general require initial data with compact support within the
computational domain, thus limiting the class of solutions that can be
studied. The goal of the present paper is to establish a spectral numerical
approach for generalised KdV equations (1) for initial data that are analytic
on the whole real line, that are slowly decreasing towards infinity, or are
bounded there. This numerical approach exhibits spectral convergence on the
whole real line with a technique similar to [12].

Both the classical KdV equation and the modified KdV equation are completely
integrable, which means they have an infinite number of conserved quantities
(for a comprehensive review on integrability see [25]). In all other cases,
the generalised KdV equations have only three conserved quantities,
$\int_{\mathbb{R}}udx$ and the $L^{2}$ norm of $u$ and the energy

(2)
$E[u]=\int_{\mathbb{R}}\left(\frac{u^{p+1}}{p(p+1)}-\frac{1}{2}u_{x}^{2}\right)dx.$

The complete integrability of the classical KdV equation made it one of the
best studied non-linear dispersive equations with a rather complete
understanding of its solutions. However, even in this case there are open
questions which motivate us to provide numerical tools to complement
analytical studies in this context. The standard inverse scattering approach
to KdV is only applicable if the Faddeev decay condition [8],

(3) $\int_{\mathbb{R}}(1+|x|)|u_{0}(x)|dx<\infty,$

holds for the initial data $u(x,0)=u_{0}(x)$. The direct scattering approach
to KdV involves the determination of the spectrum of the Schrödinger equation
for the potential $u_{0}(x)$,

$\psi_{xx}+u_{0}(x)\psi=E\psi,$

see [25]. It is known that this discrete spectrum is finite if the Faddeev
condition (3) is satisfied, see [17]. But except for the periodic case, see
for instance [1], there is no complete understanding of the case of initial
data not satisfying (3). The goal of the present paper is to provide numerical
tools to study such cases. Of course, numerically one will be only able to
study finite times and thus will not be able to address the question whether
the time evolution of such data can lead to an infinite number of solitons.

The paper is organized as follows: In section 2 we summarize a few theoretical
facts on generalised KdV equations. In section 3 we choose a compactification
of the real line and describe the numerical approach for the generalised KdV
equations. In section 4 we discuss several examples. Concluding remarks are
added in section 5.

##  2\. Theoretical preliminaries

In this section we summarize basic facts about generalised KdV equations
needed in the following.

Though the KdV equations (1) are only completely integrable for $p=2$ and
$p=3$, they have for all integer values of $p\geq 2$ a solitary travelling
wave solution which is explicitly given by $u=Q_{c}(x-x_{0}-ct)$ with
$x_{0},c=const$ and with

(4)
$Q_{c}(z)=\left(\frac{p(p+1)c}{2}\,\mbox{sech}^{2}\frac{\sqrt{c}(p-1)}{2}z\right)^{1/(p-1)}.$

Thus, we have $Q_{c}(z)=c^{1/(p-1)}Q(\sqrt{c}z)$, where we have put
$Q:=Q_{1}$. This simple scaling property of the _solitons_ allows to
concentrate on the case $c=1$. If we refer in the following to the generalised
KdV soliton, it is always implied that $c=1$. It was shown in [4] that these
solitons are linearly unstable for $p>4$. Note that the energy of the soliton
vanishes for $p=5$.

The generalised KdV equation has the following scaling invariance: $x\mapsto
x/\lambda$, $t\mapsto t/\lambda^{3}$ and $u\mapsto\lambda^{2/(p-1)}u$ with
$\lambda=const$. For $p=5$, the $L^{2}$ norm of $u$ is invariant under this
rescaling, and this case is consequently called $L^{2}$-critical. It is shown
in [18] that solutions to the $L^{2}$ critical generalised KdV equation can
have a blow-up in finite time for smooth initial data. The mechanism of the
blow-up for initial data close to the soliton is discussed in [20]. In the
present paper, we will only study the sub-critical cases, $p\leq 4$.

A convenient way to treat solutions varying on length scales of order
$1/\epsilon$ for times of order $1/\epsilon$ for $0<\epsilon\ll 1$ is to
consider the map $x\mapsto\epsilon x$, $t\mapsto\epsilon t$. This leads for
(1) to (once more we use the same symbol $u$ for the transformed and the
original solution)

(5) $u_{t}+\epsilon^{2}u_{xxx}+u^{p-1}u_{x}=0.$

The formal limit $\epsilon\to 0$ of this equation yields a generalised Hopf
equation, $u_{t}+u^{p-1}u_{x}=0$. It is known that such equations can have a
_hyperbolic blow-up_ , i.e., shocks for general smooth initial data, for
instance for data with a single hump. The generic _break-up_ of such solutions
at a point $(x_{c},t_{c},u_{c})$, see for instance the discussion in [7] and
references therein, is characterized by the equations

$\displaystyle a(u_{c})t_{c}+\Phi(u_{c})$ $\displaystyle=x_{c},$ (6)
$\displaystyle a^{\prime}(u_{c})t_{c}+\Phi^{\prime}(u_{c})$ $\displaystyle=0,$
$\displaystyle a^{\prime\prime}(u_{c})t_{c}+\Phi^{\prime\prime}(u_{c})$
$\displaystyle=0,$

where $a(u)=u^{p-1}$. It is known that dispersive regularizations of
dispersionless equations as (5) in our case will lead to _dispersive shock
waves_ (DSWs), i.e., rapid modulated oscillations near the shock of the
solution of the corresponding dispersionless equation for the same initial
data. Dubrovin [5, 6] presented a conjecture that the onset of a DSW is
_universal_ for a large class of dispersive equations and of initial data, and
that it is given by a special solution of the so-called Painlevé $P_{I}^{2}$
equation, see for instance [11]. This conjecture was numerically shown to
apply to the generalised KdV equations in [7]. In this paper we provide the
numerical tools to do so for larger classes of initial data than in [7],
however we leave addressing the universality conjecture in the present context
for a future work.

##  3\. Numerical approach

In this section we present the numerical approach to treat generalised KdV
equations on the compactified real line. We first introduce the
compactification which allows to study the equation on the interval $[-1,1]$
where we use a Chebyshev collocation method. The resulting system of ordinary
differential equations is then integrated in time with an implicit Runge-Kutta
scheme.

###  3.1. Compactification

To numerically treat the KdV equation, we first map the real line via the well
known map (this is the standard compactification used for Minkowski spacetime)

(7) $x=c\tan\frac{\pi l}{2},\quad l\in[-1,1],\quad c=const,$

to the interval $[-1,1]$. This implies

(8) $\partial_{x}=\frac{2}{\pi c}\cos^{2}\frac{l\pi}{2}\partial_{l}.$

The role of the constant $c$ is to control the numerical resolution in various
parts of the real line within certain limits. This is illustrated in Fig. 1
where we have introduced _Chebyshev collocation points_ for $l\in[-1,1]$,
i.e.,

(9) $l_{n}=\cos(n\pi/N),\quad n=0,1,\ldots,N,\quad N\in\mathbb{N}.$

It can be seen in Fig. 1 that the density of the points near $x=0$ is higher
for smaller $c$ (numerically the function $\tilde{v}$ is studied as a function
of $l$, but since in applications the dependence on $x$ is more important, we
plot its $x$-dependence which can be obtained via (7)). Note, however, that
the spectral methods we apply in this paper are global. This means that a high
resolution in part of the studied domain is not necessarily beneficial, only
the overall resolution on the whole interval is important. Therefore we
generally apply values of $c$ close to 1.

Figure 1. Distribution of the Chebyshev collocation points (9) on a Lorentzian
profile under the map (7) for $N=800$; on the left for $c=0.1$, in the middle
for $c=1$, on the right for $c=10$.

###  3.2. Boundary conditions

The map (7) transforms the KdV equation (1) on the real line to an equation on
the interval $[-1,1]$, which is singular at the points $l=\pm 1$. Because of
this singular behavior, no boundary conditions need to be imposed there.
However, in practice it is useful to give boundary conditions at these points
to stabilize the numerical approaches. We apply a vanishing condition for $u$
at these points, and a _clamped boundary condition_ for $l=-1$, i.e., the
three conditions (in an abuse of notation, we denote $u(x,t)$ and $u(l,t)$
with the same letter)

(10) $u(l,t)\biggr{\rvert}_{l=1}=0,\quad u(l,t)\biggr{\rvert}_{l=-1}=0,\quad
u_{l}(l,t)\biggr{\rvert}_{l=-1}=0.$

The approach we present here can be generalised to functions $u$ which do not
tend to 0 for $|x|\to\infty$, but which are bounded there. In this case we
write

(11) $u=v+V,\quad V=A\frac{1+l}{2}+B\frac{(1+l)^{2}}{4}+C\frac{1-l}{2},$

where $A$, $B$, $C$ are constants such that $v(l=\pm 1)=v_{l}(l=-1)=0$. To
treat the clamped boundary condition for $l=-1$, we use as in [22] the ansatz

(12) $v=(1+l)\tilde{v}.$

This leads for (1) to the equation

(13)
$\tilde{v}_{t}+\frac{1}{1+l}[(1+l)\tilde{v}+V]_{xxx}+\frac{1}{1+l}[(1+l)\tilde{v}+V]^{p}[(1+l)\tilde{v}+V]_{x}=0$

which has to be solved for all $t$ with the condition $\tilde{v}(\pm 1)=0$.

###  3.3. Chebyshev differentiation matrices

The dependence of $\tilde{v}$ in (13) on $l$ will be treated in standard way
via Lagrange interpolation of $\tilde{v}$ on Chebyshev collocation points (9)
as discussed in [22]. A derivative of $\tilde{v}$ with respect to $l$ is then
approximated via the derivative of the Lagrange polynomial. This leads to the
action of a matrix on the vector
$\tilde{v}=(\tilde{v}(l_{0}),\ldots,\tilde{v}_{N})$ (again we use the same
symbol for the function $\tilde{v}$ and the vector $\tilde{v}$), the well
known _Chebyshev differentiation matrices_ $D$, see e.g., [23, 24]. This means
with (8) that the derivatives $\partial_{x}$ are approximated by

(14) $\partial_{x}\approx\frac{2}{\pi
c}\mbox{diag}\left(\cos^{2}\frac{l\pi}{2}\right)D,$

where the diagonal matrix has the components
$(\cos^{2}\frac{l_{0}\pi}{2},\ldots,\cos^{2}\frac{l_{N}\pi}{2})$.

The Lagrange interpolation of a function on Chebyshev collocation points is
closely related to an expansion of the function in terms of Chebyshev
polynomials $T_{n}$, $n=0,1,\ldots$

(15) $\tilde{v}(l)\approx\sum_{n=0}^{N}v_{n}T_{n}(l),$

see the discussion in [22]. As shown again in [22], the Chebyshev coefficients
$v_{n}$, $n=0,1,\ldots,N$ can be computed efficiently via a fast cosine
transform which is closely related to the fast Fourier transform. It is also
known that the Chebyshev coefficients for a function analytic on $[-1,1]$
decrease exponentially, and that the numerical error in approximating a
function $\tilde{v}$ via (15) is of the order of the first omitted
coefficients $v_{n}$ in the Chebyshev series.

###  3.4. Time integration

After the discretisation in space equation (13) becomes an $N+1$-dimensional
system of ordinary differential equations (ODEs) in $t$ of the form
$\tilde{v}_{t}=f(\tilde{v})$ which can be numerically integrated in time with
standard techniques. The discussion in [22] shows that Chebyshev
differentiation matrices have a conditioning of the order
$\mbox{cond}(D^{3})=O(N^{6})$. Thus explicit time integration schemes are
problematic since stability conditions would necessitate prohibitively small
time steps. Therefore, here we apply an implicit method, and since we are
interested in capturing rapid oscillations in the expected DSWs, we use a
fourth order method.

Concretely, we apply a fourth order Runge-Kutta (IRK4) scheme, also called the
Hammer-Hollingsworth method, a 2-stage Gauss scheme. The general formulation
of an $s$-stage Runge–Kutta method for the initial value problem
$\tilde{v}^{\prime}=f(\tilde{v},t),\,\,\,\,\tilde{v}(t_{0})=\tilde{v}_{0}$
reads:

(16)
$\displaystyle\tilde{v}_{n+1}=\tilde{v}_{n}+h\underset{i=1}{\overset{s}{\sum}}\,b_{i}K_{i},$
(17) $\displaystyle
K_{i}=f\left(t_{n}+c_{i}h,\,\tilde{v}_{n}+h\underset{j=1}{\overset{s}{\sum}}\,a_{ij}K_{j}\right),$

where $b_{i},\,a_{ij},\,\,i,j=1,...,s$ are real numbers and
$c_{i}=\underset{j=1}{\overset{s}{\sum}}\,a_{ij}$. For the IRK4 method used
here, one has $c_{1}=\frac{1}{2}-\frac{\sqrt{3}}{6}$,
$c_{2}=\frac{1}{2}+\frac{\sqrt{3}}{6}$, $a_{11}=a_{22}=1/4$,
$a_{12}=\frac{1}{4}-\frac{\sqrt{3}}{6}$,
$a_{21}=\frac{1}{4}+\frac{\sqrt{3}}{6}$ and $b_{1}=b_{2}=1/2$.

Applying IRK4 to (13) we get the following system,

$\displaystyle\mathcal{L}K_{1}$
$\displaystyle=-\frac{1}{1+l}[(1+l)(\tilde{v}+ha_{12}K_{2})+V]_{xxx}$
$\displaystyle-\frac{1}{1+l}[(1+l)(\tilde{v}+ha_{11}K_{1}+ha_{12}K_{2})+V]^{p}[(1+l)(\tilde{v}+ha_{11}K_{1}+ha_{12}K_{2})+V]_{x},$
$\displaystyle\mathcal{L}K_{2}$
$\displaystyle=-\frac{1}{1+l}[(1+l)(\tilde{v}+ha_{21}K_{1})+V]_{xxx}$ (18)
$\displaystyle-\frac{1}{1+l}[(1+l)(\tilde{v}+ha_{21}K_{1}+ha_{22}K_{2})+V]^{p}[(1+l)(\tilde{v}+ha_{21}K_{1}+ha_{22}K_{2})+V]_{x},$

where

$\mathcal{L}=\hat{1}+ha_{11}\frac{1}{1+l}\partial_{xxx}(1+l).$

Recall that $\partial_{x}$ is approximated in (18) via (14), and the third
derivative with respect to $x$ is approximated as the cubic power of this.

The system (18) will be solved iteratively with a simplified Newton iteration.
This means that in each step of the iteration the new $K_{1}$ and $K_{2}$ are
obtained by inverting the operator $\mathcal{L}$ only instead of the full
Jacobian. The vanishing boundary conditions for $\tilde{v}$ and thus for
$K_{1}$, $K_{2}$ are imposed as in [22]: the equations
$\mathcal{L}K_{i}=F_{i}$, $i=1,2$, are solved by considering only the
components $1,\ldots,N-1$ of the $K_{i}$; this means that we consider the
reduced equations

$\sum_{m=1}^{N-1}\mathcal{L}_{nm}K_{i,m}=F_{i,n},\quad n=0,\ldots,N-1,\quad
i=1,2,$

and solve for $K_{i,1},\ldots,K_{i,N-1}$ only since the values
$K_{i,0}=K_{i,N}=0$ are imposed.

The resolution in time can be controlled via the conserved quantities of the
generalised KdV equation. We consider in general the energy for functions
vanishing at infinity. For functions which are just bounded at infinity, we
consider a linear combination of the energy and the $L^{2}$ norm of the
solution,

(19) $\tilde{E}=\int_{\mathbb{R}}\left(\frac{u^{p+1}-\lambda
u^{2}}{p(p+1)}-\frac{1}{2}u_{x}^{2}\right)dx,$

where the constant $\lambda$ is chosen such that the integrand is bounded at
infinity. The conserved quantities will in actual computations depend on time
due to numerical errors. But as discussed for instance in [14], the
conservation of these quantities controls the numerical error which is in
general overestimated by up to two orders of magnitude.

##  4\. Examples

In this section we study two types of examples which illustrate the potential
of the presented numerical approach. First we consider initial data in the
form of a mollified (smoothed out) step function. Then we study initial data
not satisfying the Faddeev condition
$\int^{+\infty}_{-\infty}(1+|x|)|u(x)|dx<\infty$, see [25], but nevertheless
vanishing for $|x|\to\infty$. These examples are studied for two types of
nonlinearity, for $p=2$, the completely integrable KdV equation, and for
$p=4$, a non-integrable generalised KdV equation discussed for instance in
[19]. The latter is still sub-critical which means that there is no blow-up
for sufficiently regular initial data.

###  4.1. Mollified step initial data

We consider initial data of the form

(20) $u(x,0)=\begin{cases}1&x<0\\\ \exp(-x^{2n})&x\geq 0\end{cases},$

where $n\in\mathbb{N}$. In Fig. 2 we show these data for $n=4$ on the left,
and the corresponding function $\tilde{v}$ on the right (one has $A=-B=C=1$).

######  Remark 4.1.

The function (20) is analytic everywhere except at zero, where it is
$C^{2n-1}$, thus the convergence rate of a spectral method is expected to be
algebraic. Nevertheless, in practice this does not have a detrimental effect
on our approach and, as we can see below in figure 5 on the right, the
behavior of Chebyshev coefficients is, due to the finite precision used,
virtually the same as in the analytic case.

Figure 2. Initial data (20) for $n=4$ on the left, and the corresponding
$\tilde{v}=\tilde{v}\left(l(x)\right)$ the right.

For the time evolution of these data, we use $c=2$, $N=600$ and $N_{t}=1000$
time steps for $t\in[0,0.01]$. The resulting solution to the KdV equation can
be seen in Fig. 3. The formation of a dispersive shock wave is clearly
visible.

Figure 3. Solution to the KdV equation (1) with $p=2$ for the initial data
(20) for $n=4$ in dependence of time.

The slow decrease of the amplitude of the oscillations towards infinity,
similar to the behaviour of the Airy function, is challenging for any
numerical method. The Chebyshev coefficients $v_{n}$ (15) of the solution are
shown in Fig. 4, on the left for $t=0$, on the right for $t=0.01$. They
decrease exponentially to the order of the rounding error for the initial data
indicating that an analytic (within numerical precision, see remark 4.1)
function is numerically well resolved. The algebraic decay of the spectral
coefficients for $t=0.01$ indicates an oscillatory singularity at infinity as
for the Airy function. The spatial resolution is thus of the order of
$10^{-4}$. The relative conservation of the modified energy (19) is during the
whole computation of the order of $10^{-4}$. This means the solution is
obtained to better than plotting accuracy.

Figure 4. The Chebyshev coefficients (15), on the left for the mollified step
initial data (20) on the right for the solution shown in Fig. 3 for $t=0.01$

Note that the DSW is not the same as in the case of an exact step, the
classical Gurevitch-Pitaevski problem [13]. But one can for instance verify
that this is the correct solution by considering a finite step smoothed out at
both sides,

(21) $u(x,0)=\begin{cases}1&x_{0}<x<0\\\ \exp(-x^{2n})&x\geq 0\\\
\exp(-(x-x_{0})^{2n})&x\leq x_{0}\end{cases}$

which can be conveniently treated with Fourier methods as in [14] to which the
reader is referred for details and references. We use $N=2^{12}$ Fourier modes
for $x\in 10[-\pi,\pi]$ and $N_{t}=1000$ time steps for a fourth order
exponential time differencing method. In Fig. 5 we show on the left the
solution of Fig. 3 for $t=0.01$, and for the initial data (21) with $n=4$ and
$x_{0}=-5\pi$ at the same time.

Figure 5. Solution to the KdV equation (1) with $p=2$ for the initial data
(20) on the left, and for the initial data (21) on the right, both for $n=4$
and $t=0.01$.

The solution to the generalised KdV equation with $p=4$ for the same initial
data as in Fig. 2 can be seen in Fig. 6. We have used the same numerical
parameters as for the case $p=2$, and we obtain the same numerical resolution.
The form of the DSW is very similar to one for the standard KdV equation.

Figure 6. Solution to the generalised KdV equation (1) with $p=4$ for the
initial data (20) for $n=4$ in dependence of time.

###  4.2. Slowly decaying initial data

In this subsection we consider initial data not satisfying the Faddeev
condition, and we are interested in the long time behavior of the
corresponding KdV solutions which is done by introducing a small parameter
$\epsilon$ in (5). Concretely, we study initial data of the form

(22) $u(x,0)=\frac{1}{(1+x^{2})^{a}},\quad a=\frac{1}{2},1.$

We use $c=2$, $N=800$, and $N_{t}=10^{4}$ time steps for $t\in[0,10]$. In Fig.
7 we show the KdV solution ($p=2$) in (5) for the initial data (22) for
$\epsilon=10^{-1}$ and $a=1$ in dependence of time. It can be seen that
several solitons appear.

Figure 7. Solution to the KdV equation (1) with $p=2$ for the initial data
(22) for $a=1$ in dependence of time.

The corresponding KdV solution for the initial data (22) with $a=1/2$ and
$\epsilon=10^{-1}$ can be seen in Fig. 8. Note that in contrast to the case
$a=1$, the initial data do not satisfy the clamped boundary conditions for
$x\to-\infty$, one has $A=-B=\pi/2$ and $C=0$ in (11).

Figure 8. Solution to the KdV equation (1) with $p=2$ for the initial data
(22) for $a=1/2$ in dependence of time.

The solutions at the final time of Fig. 7 and 8 can be seen in Fig. 9, on the
left for $a=1/2$, on the right for $a=1$. The slower decay towards infinity of
the initial data with $a=1/2$ can be recognized. But at the time $t=10$, one
observes the same number of solitons in both cases. The peaks in the solutions
have been fitted to the solitons (4) which are shown in green in the same
figure. It can be seen that the solitons are not yet fully separated from the
background, but that they can be already clearly identified at this early
stage.

Figure 9. Solution to the KdV equation (1) with $p=2$ for the initial data
(22) for $t=10$, on the left for $a=1/2$, on the right for $a=1$; in green
fitted solitons (4).

The relative computed energy is in both cases conserved to the order of
$10^{-10}$. The Chebyshev coefficients for $t=10$ are shown in Fig. 10, on the
left for $a=1/2$, on the right for $a=1$. It can be seen that the coefficients
decrease as expected exponentially, and that the solutions are well resolved
in space as well.

Figure 10. Solution to the KdV equation (1) with $p=2$ for the initial data
(22) for $t=10$, on the left for $a=1/2$, on the right for $a=1$.

If the same initial data as in Fig. 9 are considered for the generalised KdV
equation (5) with $p=4$, one obtains for $t=10$ the solutions shown in Fig.
11. The solitons are here much more peaked than in the KdV case of Fig. 9
which is also illustrated by the fit to the solitons. Consequently the same
numerical parameters as there lead for the generalised KdV solution to a lower
resolution: the relative conservation of the energy is of the order of
$10^{-4}$, and Chebyshev coefficients decrease still exponentially, but only
to the order of $10^{-6}$ in this case.

Figure 11. Solution to the KdV equation (1) with $p=4$ for the initial data
(22) for $t=10$, on the left for $a=1/2$, on the right for $a=1$.

##  5\. Outlook

In this paper we have presented a numerical approach for generalised KdV
equations on the compactified real line which allows to approximate functions
which are smooth on $\mathbb{R}\cup\\{\infty\\}$ with spectral accuracy, i.e.,
with a numerical error decreasing exponentially with the number of collocation
points. The time integration is performed with an implicit fourth order
method. One direction of further research will be to improve the efficiency of
the time integration, ideally an explicit approach, for instance similar to
the approach of [16] in the context of the Schrödinger equation.

Of special interest is, however, the application of the techniques of the
present paper to the numerical study of blow-up in the context of generalised
KdV equations, i.e., for (1) with $p\geq 5$. The current approach would allow
to study the dynamically rescaled generalised KdV equations, see for instance
[15] without the problems there related to the use of Fourier methods. In this
context it would be beneficial to apply a multidomain spectral method as in
[3] for Schrödinger equations where the compactified real axis is divided into
several domains each of which is mapped to the interval $[-1,1]$. This allows
for a more efficient allocation of numerical resolution than via the choice of
the parameter $c$ in (7), in particular a higher resolution near the expected
blow-up. To this end, matching conditions at the domain boundaries (the
solution $u$ has to be $C^{2}$ there) have to imposed which is numerically
problematic. This will be a subject of further research.

## References

  * [1] Belokolos E, Bobenko A, Enolskii V, Its A and Matveev V 1994 Algebro-Geometric Approach to Nonlinear Integrable Equations, Springer Series in Nonlinear Dynamics (Berlin: Springer)
  * [2] J. Bérenger. A perfectly matched layer for the absorption of electromagnetic waves. J. Comput. Phys. 114, 185-200, 1994.
  * [3] M. Birem and C. Klein, Multidomain spectral method for Schrödinger equations, Adv. Comp. Math., 42(2), 395-423 DOI 10.1007/s10444-015-9429-9 (2016)
  * [4] J. L. Bona, P. E. Souganidis, W. A. Strauss, Stability and instability of solitary waves of Korteweg-de Vries type, Proc. R. Soc. Lond. A 411 (1987) 395 - 412.
  * [5] B. Dubrovin, On Hamiltonian perturbations of hyperbolic systems of conservation laws, II: universality of critical behaviour, Comm. Math. Phys. 267 (2006) 117 - 139.
  * [6] B. Dubrovin, On universality of critical behaviour in Hamiltonian PDEs, Amer. Math. Soc. Transl. 224 (2008) 59-109.
  * [7] B. Dubrovin, T. Grava and C. Klein, Numerical Study of breakup in generalised Korteweg-de Vries and Kawahara equations, SIAM J. Appl. Math., Vol 71, 983-1008 (2011).
  * [8] L.D. Faddeev, On the relation between the S-matrix and potential for the one dimensional Schrödinger operator, Dok. Akad.Nauk SSSR 121 (1958), 63-66, see also Amer. Math. Soc. Transl; (2) 65 (1967), 139-166.
  * [9] A.S. Fokas: The generalised Dirichlet-to-Neumann map for certain non linear evolution PDEs. Comm. Pure Appl. Math. 58(5), 639-670 (2005)
  * [10] T. Grava and C. Klein, Numerical study of the small dispersion limit of the Korteweg-de Vries equation and asymptotic solutions, Physica D, 10.1016/j.physd.2012.04.001 (2012).
  * [11] T. Grava, A. Kapaev, and C. Klein, On the tritronquée solutions of $P^{2}_{I}$ , Constr. Approx. 41, 425 -466, DOI 10.1007/s00365-015-9285-3 (2015).
  * [12] C.E. Grosch and S.A. Orszag, Numerical solution of problems in unbounded regions: coordinate transforms, J. Comput. Phys. 25, 273-296 (1977).
  * [13] A. V. Gurevich, L. P. Pitaevskii, Nonstationary structure of a collisionless shock wave. Eksper. Teoret. Fiz. 65 (1973), no. 8, 5901-7604; translation in Soviet Physics JETP 38 (1974), no. 2, 2911-7297.
  * [14] C. Klein, Fourth order time-stepping for low dispersion Korteweg-de Vries and nonlinear Schrödinger equation, ETNA Vol. 29 116-135 (2008).
  * [15] C. Klein and R. Peter, Numerical study of blow-up in solutions to generalised Korteweg-de Vries equations, Physica D 304-305 (2015), 52-78 DOI 10.1016/j.physd.2015.04.003.
  * [16] C. Klein, N. Stoilov, Numerical study of the transverse stability of the Peregrine solution, Stud Appl Math. 145 (2020) 36-51. https://doi.org/10.1111/sapm.12306
  * [17] V.A. Marchenko, Sturm-Liouville operators and applications. Revised edition, AMS Chelsea Publishing vol. 373 (2001).
  * [18] Y. Martel and F. Merle, Stability of Blow-Up Profile and Lower Bounds for Blow-Up Rate for the Critical generalised KdV Equation, Ann. Math., 155, (2002), 235-280.
  * [19] Y. Martel, F. Merle, On the nonexistence of pure multi-solitons for the quartic gKdV equation. Int Math Res Notices (2015) (3): 688-739.
  * [20] Y. Martel, F. Merle, P. Raphaél, Blow up for the critical gKdV equation I: dynamics near the soliton. Acta Math. 212 (2014), no. 1, 59-140.
  * [21] T. L. Perel’man, A. Kh. Fridman, and M. M. EI’yashevich, A modified Korteweg-de Vries equation in electrohydrodynamics, Sov. Phys. JETP, Vol. 39, No.4, October 1974
  * [22] L.N. Trefethen, Spectral Methods in Matlab. SIAM, Philadelphia, PA (2000)
  * [23] www.comlab.ox.ac.uk/oucl/work/nick.trefethen
  * [24] J.A.C. Weideman, S.C. Reddy: A Matlab differentiation matrix suite. ACM TOMS 26, 465-1-7519 (2000)
  * [25] V.E. Zakharov ed., . What is integrability?. Berlin: Springer-Verlag, (1991).
  * [26] C. Zheng, A perfectly matched layer approach to the nonlinear Schrödinger wave equations. J. Comput. Phys. 227, 537-556 (2007)
  * [27] C. Zheng, Numerical simulation of a modified KdV equation on the whole real axis, Numer. Math. (2006) 105:315-335 DOI 10.1007/s00211-006-0044-z