Leonid B. Sokolinsky and Irina M. Sokolinskaya 11institutetext: South Ural
State University (National Research University)
76, Lenin prospekt, Chelyabinsk, Russia, 454080
11email<EMAIL_ADDRESS>11email<EMAIL_ADDRESS>
# FRaGenLP: A Generator of Random Linear Programming Problems for Cluster
Computing Systems

Leonid B. Sokolinsky  Irina M. Sokolinskaya The reported study was partially
funded by the Russian Foundation for Basic Research (project No.
20-07-00092-a) and the Ministry of Science and Higher Education of the Russian
Federation (government order FENU-2020-0022).

###### Abstract

The article presents and evaluates a scalable FRaGenLP algorithm for
generating random linear programming problems of large dimension $n$ on
cluster computing systems. To ensure the consistency of the problem and the
boundedness of the feasible region, the constraint system includes $2n+1$
standard inequalities, called support inequalities. New random inequalities
are generated and added to the system in a manner that ensures the consistency
of the constraints. Furthermore, the algorithm uses two likeness metrics to
prevent the addition of a new random inequality that is similar to one already
present in the constraint system. The algorithm also rejects random
inequalities that cannot affect the solution of the linear programming problem
bounded by the support inequalities. The parallel implementation of the
FRaGenLP algorithm is performed in C++ through the parallel BSF-skeleton,
which encapsulates all aspects related to the MPI-based parallelization of the
program. We provide the results of large-scale computational experiments on a
cluster computing system to study the scalability of the FRaGenLP algorithm.

###### keywords:

Random linear programming problem $\cdot$ Problem generator $\cdot$ FRaGenLP
$\cdot$ Cluster computing system $\cdot$ BSF-skeleton

##  1 Introduction

The era of big data [1, 2] has generated large-scale linear programming (LP)
problems [3]. Such problems arise in economics, industry, logistics,
statistics, quantum physics, and other fields. To solve them, high-performance
computing systems and parallel algorithms are required. Thus, the development
of new parallel algorithms for solving LP problems and the revision of current
algorithms have become imperative. As examples, we can cite the works [4, 5,
6, 7, 8]. The development of new parallel algorithms for solving large-scale
linear programming problems involves testing them on benchmark and random
problems. One of the most well-known benchmark repositories of linear
programming problems is Netlib-Lp [9]. However, when debugging LP solvers, it
is often necessary to generate random LP problems with certain
characteristics, with the dimension of the space and the number of constraints
being the main ones. The paper [10] suggested one of the first methods for
generating random LP problems with known solutions. The method allows
generating test problems of arbitrary size with a wide range of numerical
characteristics. The main idea of the method is as follows. Take as a basis an
LP problem with a known solution and then randomly modify it so that the
solution does not change. The main drawback of the method is that fixing the
optimal solution in advance significantly restricts the random nature of the
resulting LP problem.

The article [11] describes the GENGUB generator, which constructs random LP
problems with a known solution and given characteristics, such as the problem
size, the density of the coefficient matrix, the degeneracy, the number of
binding inequalities, and others. A distinctive feature of GENGUB is the
ability to introduce generalized upper bound constraints, defined to be a
(sub)set of constraints in which each variable appears at most once (i.e., has
at most one nonzero coefficient). This method has the same drawback as the
previous one: by preliminarily fixing the optimal solution, one significantly
restricts the random nature of the resulting LP problem.

The article [12] suggests a method for generating random LP problems with a
preselected solution type: bounded or unbounded, unique or multiple. Each of
these structures is generated using random vectors with integer components
whose range can be given. Next, an objective function that satisfies the
required conditions, i.e., leads to a solution of the desired type, is
obtained. The LP problem generator described in [12] is mainly used for
educational purposes and is not suitable for testing new linear programming
algorithms due to the limited variety of generated problems.

In the present paper, we suggest an alternative method for generating random
LP problems. The method has the peculiarity of generating feasible problems of
a given dimension with an unknown solution. The generated problem is fed to
the input of the tested LP solver, and the latter outputs a solution that must
be validated. The validator program (see, for example, [13]) validates the
obtained solution. The method we suggest for generating random LP problems is
named FRaGenLP (Feasible Random Generator of LP) and is implemented as a
parallel program for cluster computing systems. The rest of the article is as
follows. Section 2 provides a formal description of the method for generating
random LP problems and gives a sequential version of the FRaGenLP algorithm.
In Section 3, we discuss the parallel version of the FRaGenLP algorithm. In
Section 4, we describe the implementation of FRaGenLP using a parallel BSF-
skeleton and give the results of large-scale computational experiments on a
cluster computing system. The results confirm the efficiency of our approach.
Section 5 summarizes the obtained results and discusses plans to use the
FRaGenLP generator in the development of an artificial neural network capable
of solving large LP problems.

##  2 Method for Generating Random LP Problems

The method suggested in this paper generates random feasible bounded LP
problems of arbitrary dimension $n$ with an unknown solution. To guarantee the
correctness of the LP problem, the constraint system includes the following
_support inequalities_ :

$\left\\{{\begin{array}[]{*{20}{l}}{{x_{1}}}&{}&{}&{}&\leqslant&\alpha\\\
{}&{{x_{2}}}&{}&{}&\leqslant&\alpha\\\ {}&{}&\ddots&{}&\cdots&\cdots\\\
{}&{}&{}&{{x_{n}}}&\leqslant&\alpha\\\ {-{x_{1}}}&{}&{}&{}&\leqslant&0\\\
{}&{-{x_{2}}}&{}&{}&\leqslant&0\\\ {}&{}&\ddots&{}&\cdots&\cdots\\\
{}&{}&{}&{-{x_{n}}}&\leqslant&0\\\
{{x_{1}}}&{+{x_{2}}}&\cdots&{+{x_{n}}}&\leqslant&{(n-1)\alpha+\alpha/2}\end{array}}\right.$
(1)

Here, the positive constant $\alpha\in{\mathbb{R}_{>0}}$ is a parameter of the
FRaGenLP generator. The number of support inequalities is $2n+1$. The number
of random inequalities is determined by a parameter
$d\in{\mathbb{Z}_{\geqslant 0}}$. The total number $m$ of inequalities is
defined by the following equation:

$m=2n+1+d.$ (2)

The coefficients of the objective function are specified by the vector

$c=\theta\left({n,n-1,n-2,\ldots,1}\right),$ (3)

where the positive constant $\theta\in{\mathbb{R}_{>0}}$ is a parameter of the
FRaGenLP generator that satisfies the following condition:

$\theta\leqslant\frac{\alpha}{2}.$ (4)

From now on, we assume that the LP problem requires finding a feasible point
at which the maximum of the objective function is attained. If the number $d$
of random inequalities is zero, then FRaGenLP generates an LP problem that
includes only the support inequalities given in (1). In this case, the LP
problem has the following unique solution:

$\bar{x}=\left({\alpha,\ldots,\alpha,{\alpha/2}}\right).$ (5)

If the number $d$ of random inequalities is greater than zero, the FRaGenLP
generator adds the corresponding number of inequalities to system (1). The
coefficients ${a_{i}}=\left({{a_{i1}},\ldots,{a_{in}}}\right)$ of the random
inequality and the constant term ${b_{i}}$ on the right side are calculated
through the function $\operatorname{rand}(l,r)$, which generates a random real
number in the interval $\left[{l,r}\right]$ ($l,r\in\mathbb{R};l<r$), and the
function $\operatorname{rsgn}()$, which randomly selects a number from the set
$\left\\{{1,-1}\right\\}$:

$\begin{array}[]{*{20}{c}}{{a_{ij}}\mathrel{\vbox{\hbox{:}}{=}}\operatorname{rsgn}()\cdot\operatorname{rand}(0,{a_{\mathrm{max}}}),}\\\
{{b_{i}}\mathrel{\vbox{\hbox{:}}{=}}\operatorname{rsgn}()\cdot\operatorname{rand}(0,{b_{\mathrm{max}}}).}\end{array}$
(6)

Here, ${a_{\mathrm{max}}},{b_{\mathrm{max}}}\in{\mathbb{R}_{>0}}$ are
parameters of the FRaGenLP generator. The inequality sign is always
“$\leqslant$”. Let us introduce the following notations:

$\operatorname{f}(x)=\langle{c,x}\rangle;$ (7)
${h}=\left({{\alpha\mathord{\left/{\vphantom{\alpha
2}}\right.\kern-1.2pt}2},{{\ldots,\alpha}\mathord{\left/{\vphantom{{\ldots,\alpha}2}}\right.\kern-1.2pt}2}}\right);$
(8)
$\operatorname{dist}_{h}({a_{i}},{b_{i}})=\frac{{\left|{\langle{{a_{i}},{h}}\rangle-{b_{i}}}\right|}}{{\left\|{{a_{i}}}\right\|}};$
(9)
$\pi(h,{a_{i}},{b_{i}})=h-\frac{{\langle{{a_{i}},h}\rangle-{b_{i}}}}{{|a_{i}|}^{2}}{a_{i}}.$
(10)

Equation (7) defines the objective function of the LP problem. Here and
further on, $\langle{\cdot,\cdot}\rangle$ stands for the dot product of
vectors. Equation (8) defines the central point of the _bounding hypercube_
specified by the first $2n$ inequalities of system (1). Furthermore, Equation
(9) defines a function $\operatorname{dist}_{h}({a_{i}},{b_{i}})$ that gives
the distance from the hyperplane $\langle{{a_{i}},x}\rangle={b_{i}}$ to the
center $h$ of the bounding hypercube. Here and below,
$\left\|{}\cdot{}\right\|$ denotes the Euclidean norm. Equation (10) defines a
vector-valued function that expresses the orthogonal projection of the point
$h$ onto the hyperplane $\langle{{a_{i}},x}\rangle={b_{i}}$.

To obtain a random inequality $\langle{{a_{i}},x}\rangle\leqslant{b_{i}}$, we
calculate the coordinates of the coefficient vector ${a_{i}}$ and the constant
term ${b_{i}}$ using a pseudorandom rational number generator. The generated
random inequality is added to the constraint system if and only if the
following conditions hold:

$\langle{{a_{i}},{h}}\rangle\leqslant{b_{i}};$ (11)
$\rho<\operatorname{dist}_{h}({a_{i}},{b_{i}})\leqslant\theta;$ (12)
$\operatorname{f}\left({\pi\left({{h},{a_{i}},{b_{i}}}\right)}\right)>\operatorname{f}\left({{h}}\right);$
(13) $\forall
l\in\\{1,\ldots,i-1\\}:\neg\operatorname{like}({a_{i}},{b_{i}},{a_{l}},{b_{l}}).$
(14)

Condition (11) requires that the center of the bounding hypercube be a
feasible point for the considered random inequality. If the condition does not
hold, then the inequality $-\langle{{a_{i}},x}\rangle\leqslant-{b_{i}}$ is
added instead of $\langle{{a_{i}},x}\rangle\leqslant{b_{i}}$. Condition (12)
requires that the distance from the hyperplane
$\langle{{a_{i}},x}\rangle={b_{i}}$ to the center ${h}$ of the bounding
hypercube be greater than $\rho$ but not greater than $\theta$. The constant
$\rho\in{\mathbb{R}_{>0}}$ is a parameter of the FRaGenLP generator and must
satisfy the condition $\rho<\theta$, where $\theta$, in turn, satisfies
condition (4). Condition (13) requires that the objective function value at
the projection of the point ${h}$ onto the hyperplane
$\langle{{a_{i}},x}\rangle={b_{i}}$ be greater than the objective function
value at the point ${h}$. This condition combined with (11) and (12) cuts off
constraints that cannot affect the solution of the LP problem. Finally,
condition (14) requires that the new inequality be _dissimilar_ from all
previously added ones, including the support ones. This condition uses the
Boolean function “$\operatorname{like}$”, which determines the _likeness_ of
the inequalities $\langle{{a_{i}},x}\rangle\leqslant{b_{i}}$ and
$\langle{{a_{l}},x}\rangle\leqslant{b_{l}}$ through the following equation:

$\operatorname{like}({a_{i}},{b_{i}},{a_{l}},{b_{l}})=\left\|{\frac{{{a_{i}}}}{{\left\|{{a_{i}}}\right\|}}-\frac{{{a_{l}}}}{{\left\|{{a_{l}}}\right\|}}}\right\|<{L_{\mathrm{max}}}\wedge\left|{\frac{{{b_{i}}}}{{\left\|{{a_{i}}}\right\|}}-\frac{{{b_{l}}}}{{\left\|{{a_{l}}}\right\|}}}\right|<{S_{\mathrm{min}}}.$
(15)

The constants ${L_{\mathrm{max}}},{S_{\mathrm{min}}}\in{\mathbb{R}_{>0}}$ are
parameters of the FRaGenLP generator. In this case, the parameter
${L_{\mathrm{max}}}$ must satisfy the condition

${L_{\mathrm{max}}}\leqslant 0.7$ (16)

(we will explain the meaning of this constraint below). According to (15),
inequalities $\langle{{a_{i}},x}\rangle\leqslant{b_{i}}$ and
$\langle{{a_{l}},x}\rangle\leqslant{b_{l}}$ are _similar_ if the following two
conditions hold:

$\left\|{\frac{{{a_{i}}}}{{\left\|{{a_{i}}}\right\|}}-\frac{{{a_{l}}}}{{\left\|{{a_{l}}}\right\|}}}\right\|<{L_{\mathrm{max}}};$
(17)
$\left|{\frac{{{b_{i}}}}{{\left\|{{a_{i}}}\right\|}}-\frac{{{b_{l}}}}{{\left\|{{a_{l}}}\right\|}}}\right|<{S_{\mathrm{min}}}.$
(18)

Condition (17) evaluates the measure of parallelism of the hyperplanes
$\langle{{a_{i}},x}\rangle={b_{i}}$ and $\langle{{a_{l}},x}\rangle={b_{l}}$,
which bound the feasible regions of the corresponding inequalities. Let us
explain this. The unit vectors $e_{i}=a_{i}/\left\|a_{i}\right\|$ and
$e_{l}=a_{l}/\left\|a_{l}\right\|$ are normal to the hyperplanes
$\langle{{a_{i}},x}\rangle={b_{i}}$ and $\langle{{a_{l}},x}\rangle={b_{l}}$,
respectively. Let us introduce the notation
$\delta=\left\|e_{i}-e_{l}\right\|$. If $\delta=0$, then the hyperplanes are
parallel. If $0\leqslant\delta<{L_{\mathrm{max}}}$, then the hyperplanes are
considered to be _nearly parallel_.

Condition (18) evaluates the _closeness_ of the parallel hyperplanes
$\langle{{a_{i}},x}\rangle={b_{i}}$ and $\langle{{a_{l}},x}\rangle={b_{l}}$.
Indeed, the scalar values $\beta_{i}=b_{i}/\left\|a_{i}\right\|$ and
$\beta_{l}=b_{l}/\left\|a_{l}\right\|$ are the normalized constant terms. Let
us introduce the notation $\sigma=|\beta_{i}-\beta_{l}|$. If $\sigma=0$, then
the parallel hyperplanes coincide. If the hyperplanes are nearly parallel and
$0\leqslant\sigma<S_{\mathrm{min}}$, then they are considered to be _nearly
concurrent_.

Two linear inequalities in $\mathbb{R}^{n}$ are considered _similar_ if the
corresponding hyperplanes are nearly parallel and nearly concurrent.

The constraint (16) for the parameter ${L_{\mathrm{max}}}$ is based on the
following proposition.

###### Proposition 1

Let the two unit vectors $e,e^{\prime}\in{\mathbb{R}^{n}}$ and the angle
$\varphi<\pi$ between them be given. Then,

$\left\|{e-e^{\prime}}\right\|=\sqrt{2(1-\cos\varphi)}.$ (19)

######  Proof 2.1.

By the definition of the norm in Euclidean space, we have

$\begin{gathered}\left\|{e-e^{\prime}}\right\|=\sqrt{\sum\limits_{j}{{{\left({{e_{j}}-{{e^{\prime}}_{j}}}\right)}^{2}}}}=\sqrt{\sum\limits_{j}{\left({{e_{j}}^{2}-2{e_{j}}{{e^{\prime}}_{j}}+{{e^{\prime}}_{j}}^{2}}\right)}}=\hfill\\\
=\sqrt{\sum\limits_{j}{{e_{j}}^{2}}-2\sum\limits_{j}{{e_{j}}{{e^{\prime}}_{j}}}+\sum\limits_{j}{{{e^{\prime}}_{j}}^{2}}}=\sqrt{1-2\langle{{e_{j}},{{e^{\prime}}_{j}}}\rangle+1}.\hfill\\\
\end{gathered}$

Thus,

$\left\|{e-e^{\prime}}\right\|=\sqrt{2\left({1-\langle{{e_{j}},{{e^{\prime}}_{j}}}\rangle}\right)}.$
(20)

By the definition of the angle in Euclidean space, we have, for unit vectors,

$\langle{{e_{j}},{{e^{\prime}}_{j}}}\rangle=\cos\varphi.$

Substituting in (20) the expression obtained, we have

$\left\|{e-e^{\prime}}\right\|=\sqrt{2\left({1-\cos\varphi}\right)}.$

The proposition is proven.

It is reasonable to consider that two unit vectors $e,e^{\prime}$ are nearly
parallel if the angle between them is less than $\pi/4$. In this case,
according to (19), we have

$\left\|{e-e^{\prime}}\right\|<\sqrt{2\left({1-\cos\frac{\pi}{4}}\right)}.$

Taking into account that $\cos(\pi/4)\approx 0.707$, we obtain the required
estimate:

$\left\|{e-e^{\prime}}\right\|<0.7.$

Figure 1: Random LP problem with $n=2$, $d=5$, $\alpha=200$, $\theta=100$,
$\rho=50$, $S_{\mathrm{min}}=100$, $L_{\mathrm{max}}=0.35$,
$a_{\mathrm{max}}=1000$, and $b_{\mathrm{max}}=10\,000$

An example of a two-dimensional LP problem generated by FRaGenLP is shown in
Figure 1. The purple color indicates the line defined by the coefficients of
the objective function; the black lines correspond to the support
inequalities, and the red lines correspond to the random inequalities. For the
sake of clarity, we use green dashed lines to plot the large and the small
circles defined by the equations
${\left({{x_{1}}-100}\right)^{2}}+{\left({{x_{2}}-100}\right)^{2}}={100^{2}}$
and
${\left({{x_{1}}-100}\right)^{2}}+{\left({{x_{2}}-100}\right)^{2}}={50^{2}}$.
According to condition (12), any random line must intersect the large green
circle but not the small green circle. The semitransparent red color indicates
the feasible region of the generated LP problem.

Algorithm 1 Sequential algorithm for generating a random LP problem

Parameters:
$n,d,\alpha,\theta,\rho,S_{\mathrm{min}},L_{\mathrm{max}},a_{\mathrm{max}},b_{\mathrm{max}}$

1:$k\mathrel{\vbox{\hbox{:}}{=}}0$

2:$A\mathrel{\vbox{\hbox{:}}{=}}[\>]$

3:$B\mathrel{\vbox{\hbox{:}}{=}}[\>]$

4:$\operatorname{AddSupport}(A,B)$

5:for $j=n\ldots 1$ do $c_{j}\mathrel{\vbox{\hbox{:}}{=}}\theta\cdot j$

6:if $d=0$ goto 19

7:for $j=1\ldots n$ do
$a_{j}\mathrel{\vbox{\hbox{:}}{=}}\operatorname{rsign}()\cdot\operatorname{rand}(0,a_{\mathrm{max}})$

8:$b\mathrel{\vbox{\hbox{:}}{=}}\operatorname{rsign}()\cdot\operatorname{rand}(0,b_{\mathrm{max}})$

9:if $\langle a,h\rangle\leqslant b$ goto 12

10:for $j=1\ldots n$ do $a_{j}\mathrel{\vbox{\hbox{:}}{=}}-a_{j}$

11:$b\mathrel{\vbox{\hbox{:}}{=}}-b$

12:if $\operatorname{dist}_{h}(a,b)<\rho$ or
$\operatorname{dist}_{h}(a,b)>\theta$ goto 7

13:if
$\operatorname{f}(\operatorname{\pi}(h,a,b))\leqslant\operatorname{f}(h)$ goto
7

14:for all $(\bar{a},\bar{b})\in(A,B)$ do if
$\operatorname{like}(a,b,\bar{a},\bar{b})$ goto 7

15:$A\mathrel{\vbox{\hbox{:}}{=}}A\mathbin{+\mkern-10.0mu+}[a]$

16:$B\mathrel{\vbox{\hbox{:}}{=}}B\mathbin{+\mkern-10.0mu+}[b]$

17:$k\mathrel{\vbox{\hbox{:}}{=}}k+1$

18:if $k<d$ goto 7

19:output $A,B,c$

20:stop

Algorithm 1 represents a sequential implementation of the described method.
Step 1 assigns zero value to the counter $k$ of random inequalities. Step 2
creates an empty list $A$ to store the coefficients of the inequalities. Step
3 creates an empty list $B$ to store the constant terms. Step 4 adds the
coefficients and constant terms of the support inequalities (1) to the lists
$A$ and $B$, respectively. Step 5 generates the coefficients of the objective
function according to (3). If the parameter $d$, which specifies the number of
random inequalities, is equal to zero, then Step 6 passes the control to Step
19. Steps 7 and 8 generate the coefficients and the constant term of the new
random inequality. Step 9 checks condition (11). If the condition does not
hold, then the signs of the coefficients and the constant term are reversed
(Steps 10, 11). Step 12 checks condition (12). Step 13 checks condition (13).
Step 14 checks condition (14). Step 15 appends the coefficients of the new
random inequality to the list $A$ ($\mathbin{+\mkern-10.0mu+}$ denotes the
concatenation of lists). Step 16 appends the constant term of the new random
inequality to the list $B$. Step 17 increments the counter of added random
inequalities by one. If the number of added random inequalities has not
reached the given quantity $d$, then Step 18 passes the control to Step 7 to
generate the next inequality. Step 19 outputs the results. Step 20 stops
computations.

##  3 Parallel Algorithm for Generating Random LP Problems

Implicit loops generated by passing the control from Steps 12–14 to Step 7 of
Algorithm 1 can result in high overheads. For example, during the generation
of the LP problem represented in Figure 1, there were 112 581 returns from
Step 12 to label 7, 32 771 from Step 13, and 726 from Step 14. Therefore,
generating a large random LP problem on a commodity personal computer can take
many hours. To overcome this obstacle, we developed a parallel version of the
FRaGenLP generator for cluster computing systems. This version is presented as
Algorithm 2. It is based on the BSF parallel computation model [14, 15], which
assumes the master–slave paradigm [16]. According to the BSF model, the master
node serves as a control and communication center. All slave nodes execute the
same code but on different data.

Algorithm 2 Parallel algorithm for generating a random LP problem

Parameters:
$n,d,\alpha,\theta,\rho,S_{\mathrm{min}},L_{\mathrm{max}},a_{\mathrm{max}},b_{\mathrm{max}}$

Master

Slave (_l_ =1,…,_L_)

1:$k\mathrel{\vbox{\hbox{:}}{=}}0$

2:$A_{S}\mathrel{\vbox{\hbox{:}}{=}}[\>]$

3:$B_{S}\mathrel{\vbox{\hbox{:}}{=}}[\>]$

4:$\operatorname{AddSupport}(A_{S},B_{S})$

5:for $j=n\ldots 1$ do $c_{j}\mathrel{\vbox{\hbox{:}}{=}}\theta\cdot j$

6:output $A_{S},B_{S},c$

7:if $d=0$ goto 36

8:$A_{R}\mathrel{\vbox{\hbox{:}}{=}}[\>]$

9:$B_{R}\mathrel{\vbox{\hbox{:}}{=}}[\>]$

10:

11:

12:

13:

14:

15:

16:

17:

18:RecvFromSlaves $a^{(1)},b^{(1)},...,a^{(L)},b^{(L)}$

19:for $l=1\ldots L$ do

20: $isLike\mathrel{\vbox{\hbox{:}}{=}}false$

21: for all $(\bar{a},\bar{b})\in(A_{R},B_{R})$ do

22: if $\operatorname{like}(a^{(l)},b^{(l)},\bar{a},\bar{b})$ then

23: $isLike\mathrel{\vbox{\hbox{:}}{=}}true$

24: goto 27

25: end if

26: end for

27: if $isLike$ continue

28: $A_{R}\mathrel{\vbox{\hbox{:}}{=}}A_{R}\mathbin{+\mkern-10.0mu+}[a^{(l)}]$

29: $B_{R}\mathrel{\vbox{\hbox{:}}{=}}B_{R}\mathbin{+\mkern-10.0mu+}[b^{(l)}]$

30: $k\mathrel{\vbox{\hbox{:}}{=}}k+1$

31: if $k=d$ goto 33

32:end for

33:SendToSlaves $k$

34:if $k<d$ goto 18

35:output $A_{R},B_{R}$

36:stop

1:if $d=0$ goto 36

2:$A_{S}\mathrel{\vbox{\hbox{:}}{=}}[\>]$

3:$B_{S}\mathrel{\vbox{\hbox{:}}{=}}[\>]$

4:$\operatorname{AddSupport}(A_{S},B_{S})$

5:for $j=1\ldots n$ do

6:
$a_{j}^{(l)}\mathrel{\vbox{\hbox{:}}{=}}\operatorname{rsign}()\cdot\operatorname{rand}(0,a_{\mathrm{max}})$

7:end for

8:$b^{(l)}\mathrel{\vbox{\hbox{:}}{=}}\operatorname{rsign}()\cdot\operatorname{rand}(0,b_{\mathrm{max}})$

9:if $\langle a^{(l)},h\rangle\leq b^{(l)}$ goto 12

10:for $j=1\ldots n$ do $a_{j}^{(l)}\mathrel{\vbox{\hbox{:}}{=}}-a_{j}^{(l)}$

11:$b^{(l)}\mathrel{\vbox{\hbox{:}}{=}}-b^{(l)}$

12:if $\operatorname{dist}_{h}(a^{(l)},b^{(l)})<\rho$ goto 5

13:if $\operatorname{dist}_{h}(a^{(l)},b^{(l)})>\theta$ goto 5

14:if
$\operatorname{f}(\operatorname{\pi}(h,a^{(l)},b^{(l)}))\leqslant\operatorname{f}(h)$
goto 5

15:for all $(\bar{a},\bar{b})\in(A_{S},B_{S})$ do

16: if $\operatorname{like}(a^{(l)},b^{(l)},\bar{a},\bar{b})$ goto 5

17:end for

18:SendToMaster $a^{(l)},b^{(l)}$

19:

20:

21:

22:

23:

24:

25:

26:

27:

28:

29:

30:

31:

32:

33:RecvFromMaster $k$

34:if $k<d$ goto 5

35:

36:stop

Let us discuss Algorithm 2 in more detail. First, we look at the steps
performed by the master node. Step 1 assigns zero value to the counter of
random inequalities. Step 2 creates an empty list ${A_{S}}$ to store the
coefficients of the support inequalities. Step 3 creates an empty list
${B_{S}}$ to store the constant terms of the support inequalities. Step 4 adds
the coefficients and constant terms of the support inequalities (1) to the
lists ${A_{S}}$ and ${B_{S}}$, respectively. Step 5 generates the coefficients
of the objective function according to (3). Step 6 outputs the coefficients
and constant term of the support inequalities. If the parameter $d$, which
specifies the number of random inequalities, is equal to zero, then Step 7
passes the control to Step 36, which terminates the computational process in
the master node. Step 8 creates an empty list ${A_{R}}$ to store the
coefficients of the random inequalities. Step 9 creates an empty list
${B_{R}}$ to store the constant terms of the random inequalities. In Step 18,
the master node receives one random inequality from each slave node. Each of
these inequalities satisfies conditions (11)–(13) and is not similar to any of
the support inequalities. These conditions are ensured by the slave nodes. In
the loop consisting of Steps 19–32, the master node checks all received random
inequalities for similarity with the random inequalities previously included
in the lists ${A_{R}}$ and ${B_{R}}$. The similar new inequalities are
rejected, and the dissimilar ones are added to the lists ${A_{R}}$ and
${B_{R}}$. In this case, the inequality counter is increased by one each time
some inequality is added to the lists. If the required number of random
inequalities has already been reached, then Step 31 performs an early exit
from the loop. Step 33 sends the current number of added random inequalities
to the slave nodes. If this quantity is less than $d$, then Step 34 passes the
control to Step 18, which requests a new portion of random inequalities from
the slave nodes. Otherwise, Step 35 outputs the results, and Step 36
terminates the computational process in the master node.

Let us consider now the steps performed by the $l$-th slave node. If the
parameter $d$, which specifies the number of random inequalities, is equal to
zero, then Step 1 passes the control to Step 36, which terminates the
computational process in the slave node. Otherwise, Steps 2 and 3 create the
empty lists ${A_{S}}$ and ${B_{S}}$ to store the support inequalities. Step 4
adds the coefficients and constant terms of the support inequalities (1) to
the lists ${A_{S}}$ and ${B_{S}}$, respectively. Steps 5–8 generate a new
random inequality. Step 9 checks condition (11). If this condition does not
hold, then the signs of the coefficients and the constant term are reversed
(Steps 10 and 11). Steps 12–14 check conditions (12) and (13). Steps 15–17
check the similarity of the generated inequality to the support inequalities.
If any one of these conditions does not hold, then the control is passed to
Step 5 to generate a new random inequality. If all conditions hold, then Step
18 sends the constructed random inequality to the master node. In Step 33 ,
the slave receives from the master the current number of obtained random
inequalities. If this quantity is less than the required number, then Step 34
passes the control to Step 5 to generate a new random inequality. Otherwise,
Step 36 terminates the computational process in the slave node.

##  4 Software Implementation and the Computational Experiments

We implemented the parallel Algorithm 2 in C++ through the parallel BSF-
skeleton [17], which is based on the BSF parallel computation model [14] and
encapsulates all aspects related to the parallelization of the program using
the MPI library [18].

The BSF-skeleton requires the representation of the algorithm in the form of
operations on lists using the higher-order functions _Map_ and _Reduce_ ,
defined by the Bird–Meertens formalism [19]. The required representation can
be constructed as follows. Set the length of the _Map_ and _Reduce_ lists
equal to the number of slave MPI processes. Define the _Map_ list items as
empty structures:

struct PT_bsf_mapElem_T{ } .

Each element of the _Reduce_ list stores the coefficients and the constant
term of one random inequality $\langle{a,x}\rangle\leqslant b$:

struct PT_bsf_reduceElem_T{ float a[n]; float b} .

Each slave MPI process generates one random inequality using the _PC_bsf_MapF_
function, which executes Steps 5–17 of Algorithm 2. The slave MPI process
stores the inequality that satisfies all conditions to its local _Reduce_ list
consisting of a single item. The master MPI process receives the generated
elements from the slave MPI processes and places them in its _Reduce_ list
(this code is implemented in the problem-independent part of the BSF-
skeleton). After that, the master MPI process checks each obtained inequality
for similarity with the previously added ones. If no matches are found, the
master MPI process adds the inequality just checked to its local _Reduce_
list. These actions, corresponding to Steps 19–32 of Algorithm 2, are
implemented as the standard function _PC_bsf_ProcessResults_ of the BSF-
skeleton. The source code of the FRaGenLP parallel program is freely available
on the Internet at https://github.com/leonid-sokolinsky/BSF-LPP-Generator.

Table 1: Specifications of the “Tornado SUSU” computing cluster Parameter | Value
---|---
Number of processor nodes | 480
Processor | Intel Xeon X5680 (6 cores, 3.33 GHz)
Processors per node | 2
Memory per node | 24 GB DDR3
Interconnect | InfiniBand QDR (40 Gbit/s)
Operating system | Linux CentOS

Using the program, we conducted large-scale computational experiments on the
cluster computing system “Tornado SUSU” [20]. The specifications of the system
are given in Table 1. The computations were performed for several dimensions,
namely $n=3000$, $n=5500$, and $n=15\,000$. The total numbers of inequalities
were, respectively, $6301$, $10\,001$, and $31\,501$. The corresponding
numbers of random inequalities were $300$, $500$, and $1500$, respectively.
Throughout the experiments, we used the following parameter values:
$\alpha=200$ (the length of the bounding hypercube edge), $\theta=100$ (the
radius of the large hypersphere), $\rho=50$ (the radius of the small
hypersphere), ${L_{\mathrm{max}}}=0.35$ (the upper bound of _near parallelism_
for hyperplanes), ${S_{\mathrm{min}}}=100$ (the minimum acceptable closeness
for hyperplanes), ${a_{\mathrm{max}}}=1000$ (the upper absolute bound for the
coefficients), and ${b_{\mathrm{max}}}=10\,000$ (the upper absolute bound for
the constant terms).

The results of the experiments are shown in Figure 2. Generating a random LP
problem with $31\,501$ constraints with a configuration consisting of a master
node and a slave node took 12 minutes. Generating the same problem with a
configuration consisting of a master node and $170$ slave nodes took 22
seconds. The analysis of the results showed that the scalability bound (the
maximum of the speedup curve) of the algorithm significantly depends on the
dimension of the problem. For $n=3000$, the scalability bound was 50 processor
nodes approximately. This bound increased up to 110 nodes for $n=5000$, and to
200 nodes for $n=15\,000$. A further increase in problem size causes the
processor nodes to run out of memory. It should be noted that the scalability
bound of the algorithm significantly depends on the number of random
inequalities too. Increasing this number by a factor of 10 resulted in a
twofold reduction of the scalability bound. This is because an increase in the
number of slave nodes results in a significant increase in the portion of
sequential computations performed by the master node in Steps 19–32, during
which the slave nodes are idle.

Figure 2: Speedup curves of the FRaGenLP parallel algorithm for various
dimensions

##  5 Conclusions

In this paper, we described the parallel FRaGenLP algorithm for generating
random feasible bounded LP problems on cluster computing systems. In addition
to random inequalities, the generated constraint systems include a standard
set of inequalities called _support inequalities_. They ensure the boundedness
of the feasible region of the LP problem. In geometric terms, the feasible
region of the support inequalities is a hypercube with edges adjacent to the
coordinate axes, and the vertex that is farthest from the origin is cut off.
The objective function is defined in such a manner that its coefficients
decrease monotonically. The coefficients and constant terms of the random
inequalities are obtained using a random number generator. If the feasible
region of a randomly generated inequality does not include the center of the
bounding hypercube, then the sign of the inequality is reversed. Furthermore,
not every random inequality is included in the constraint system. The random
inequalities that cannot affect the solution of the LP problem for a given
objective function are rejected. The inequalities, for which the bounding
hyperplane intersects a small hypersphere located at the center of the
bounding hypercube are also rejected. This ensures the feasibility of the
constraint system. Moreover, any random inequality that is “similar” to at
least one of the inequalities already added to the system (including the
support ones) is also rejected. To define the “similarity” of inequalities,
two formal metrics are introduced for bounding hyperplanes: the measure of
parallelism and the measure of closeness.

The parallel algorithm is based on the BSF parallel computation model, which
relies on the master–slave paradigm. According to this paradigm, the master
node serves as a control and communication center. All slave nodes execute the
same code but on different data. The parallel implementation was performed in
C++ through the parallel BSF-skeleton, which encapsulates all aspects related
to the MPI-based parallelization of the program. The source code of the
FRaGenLP generator is freely available on the Internet at
https://github.com/leonid-sokolinsky/BSF-LPP-Generator.

Using this implementation, we conducted large-scale computational experiments
on a cluster computing system. As the experiments showed, the parallel
FRaGenLP algorithm demonstrates good scalability, up to 200 processor nodes
for $n=15\,000$. Generating a random LP problem with $31\,501$ constraints
takes 22 seconds with a configuration consisting of 171 processor nodes.
Generating the same problem with a configuration consisting of a processor
node takes 12 minutes. The program was used to generate a dataset of 70 000
samples for training an artificial neural network capable of quickly solving
large LP problems.

## References

  * [1] Jagadish, H. V., Gehrke, J., Labrinidis, A., Papakonstantinou, Y., Patel, J.M., Ramakrishnan, R., Shahabi, C.: Big data and its technical challenges. Communications of the ACM. 57(7), 86–94 (2014). https://doi.org/10.1145/2611567.
  * [2] Hartung, T.: Making Big Sense From Big Data. Frontiers in Big Data. 1, 5 (2018). https://doi.org/10.3389/fdata.2018.00005.
  * [3] Sokolinskaya, I., Sokolinsky, L.B.: On the Solution of Linear Programming Problems in the Age of Big Data. In: Sokolinsky, L. and Zymbler, M. (eds.) Parallel Computational Technologies. PCT 2017. Communications in Computer and Information Science, vol. 753. pp. 86–100. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-67035-5_7.
  * [4] Sokolinsky, L.B., Sokolinskaya, I.M.: Scalable Method for Linear Optimization of Industrial Processes. In: Proceedings — 2020 Global Smart Industry Conference, GloSIC 2020. pp. 20–26. Article number 9267854. IEEE (2020). https://doi.org/10.1109/GloSIC50886.2020.9267854.
  * [5] Mamalis, B., Pantziou, G.: Advances in the Parallelization of the Simplex Method. In: Zaroliagis, C., Pantziou, G., and Kontogiannis, S. (eds.) Algorithms, Probability, Networks, and Games. Lecture Notes in Computer Science, vol. 9295. pp. 281–307. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-24024-4_17.
  * [6] Huangfu, Q., Hall, J.A.J.: Parallelizing the dual revised simplex method. Mathematical Programming Computation. 10(1), 119–142 (2018). https://doi.org/10.1007/s12532-017-0130-5.
  * [7] Tar, P., Stagel, B., Maros, I.: Parallel search paths for the simplex algorithm. Central European Journal of Operations Research. 25(4), 967–984 (2017). https://doi.org/10.1007/s10100-016-0452-9.
  * [8] Yang, L., Li, T., Li, J.: Parallel predictor-corrector interior-point algorithm of structured optimization problems. In: 3rd International Conference on Genetic and Evolutionary Computing, WGEC 2009. pp. 256–259 (2009). https://doi.org/10.1109/WGEC.2009.68.
  * [9] Gay, D.M.: Electronic mail distribution of linear programming test problems. Mathematical Programming Society COAL Bulletin. (13), 10–12 (1985).
  * [10] Charnes, A., Raike, W.M., Stutz, J.D., Walters, A.S.: On Generation of Test Problems for Linear Programming Codes. Communications of the ACM. 17(10), 583–586 (1974). https://doi.org/10.1145/355620.361173.
  * [11] Arthur, J.L., Frendewey, J.O.: GENGUB: A generator for linear programs with generalized upper bound constraints. Computers and Operations Research. 20(6), 565–573 (1993). https://doi.org/10.1016/0305-0548(93)90112-V.
  * [12] Castillo, E., Pruneda, R.E., Esquivel, Mo.: Automatic generation of linear programming problems for computer aided instruction. International Journal of Mathematical Education in Science and Technology. 32(2), 209–232 (2001). https://doi.org/10.1080/00207390010010845.
  * [13] Dhiflaoui, M., Funke, S., Kwappik, C., Mehlhom, K., Seel, M., Schtmer, E., Schulte, R., Weber, D.: Certifying and Repairing Solutions to Large LPs How Good are LP-solvers? In: SODA’03: Proceedings of the fourteenth annual ACM–SIAM symposium on Discrete algorithms. pp. 255–256. Society for Industrial and Applied Mathematics, USA (2003).
  * [14] Sokolinsky, L.B.: BSF: A parallel computation model for scalability estimation of iterative numerical algorithms on cluster computing systems. Journal of Parallel and Distributed Computing. 149, 193–206 (2021). https://doi.org/10.1016/j.jpdc.2020.12.009.
  * [15] Sokolinsky, L.B.: Analytical Estimation of the Scalability of Iterative Numerical Algorithms on Distributed Memory Multiprocessors. Lobachevskii Journal of Mathematics. 39(4), 571–575 (2018). http://dx.doi.org/10.1134/S1995080218040121.
  * [16] Sahni, S., Vairaktarakis, G.: The master–slave paradigm in parallel computer and industrial settings. Journal of Global Optimization. 9(3–4), 357–377 (1996). https://doi.org/10.1007/BF00121679.
  * [17] Sokolinsky, L.B.: BSF-skeleton. User manual. arXiv:2008.12256 [cs.DC]. (2020).
  * [18] Gropp, W.: MPI 3 and Beyond: Why MPI Is Successful and What Challenges It Faces. In: Traff, J.L., Benkner, S., and Dongarra, J.J. (eds.) Recent Advances in the Message Passing Interface. EuroMPI 2012. Lecture Notes in Computer Science, vol. 7490. pp. 1–9. Springer, Berlin, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33518-1_1.
  * [19] Bird, R.S.: Lectures on Constructive Functional Programming. In: Broy, M. (ed.) Constructive Methods in Computing Science. NATO ASI Series F: Computer and Systems Sciences, vol. 55. pp. 151–216. Springer, Berlin, Heidlberg (1988).
  * [20] Kostenetskiy, P., Semenikhina, P.: SUSU Supercomputer Resources for Industry and fundamental Science. In: Proceedings — 2018 Global Smart Industry Conference, GloSIC 2018, art. no. 8570068. p. 7. IEEE (2018). https://doi.org/10.1109/GloSIC.2018.8570068.


* (13) M. Berkooz, M. Rozali, and N. Seiberg, Matrix description of M theory on T**4 and T**5, Phys. Lett. B 408 (1997) 105–110, [hep-th/9704089].
  * (14) O. Aharony, A Brief review of ’little string theories’, Class. Quant. Grav. 17 (2000) 929–938, [hep-th/9911147].
  * (15) D. Kutasov, Introduction to little string theory, ICTP Lect. Notes Ser. 7 (2002) 165–209.
  * (16) A. Giveon, N. Itzhaki, and D. Kutasov, $\mathrm{T}\overline{\mathrm{T}}$ and LST, JHEP 07 (2017) 122, [arXiv:1701.05576].
  * (17) G. Giribet, $T\bar{T}$-deformations, AdS/CFT and correlation functions, JHEP 02 (2018) 114, [arXiv:1711.02716].
  * (18) M. Asrat, A. Giveon, N. Itzhaki, and D. Kutasov, Holography Beyond AdS, Nucl. Phys. B 932 (2018) 241–253, [arXiv:1711.02690].
  * (19) S. Chakraborty, A. Giveon, and D. Kutasov, Comments on single-trace $T\overline{T}$ holography, JHEP 06 (2023) 018, [arXiv:2303.12422].
  * (20) S. Chakraborty, G. Katoch, and S. R. Roy, Holographic complexity of LST and single trace $T\overline{T}$, JHEP 03 (2021) 275, [arXiv:2012.11644].
  * (21) S. Chakraborty, A. Giveon, and D. Kutasov, Momentum in Single-trace $T\bar{T}$ Holography, arXiv:2304.09212.
  * (22) S. Georgescu and M. Guica, Infinite $\mathrm{T\bar{T}}$-like symmetries of compactified LST, arXiv:2212.09768.
  * (23) O. Aharony and N. Barel, Correlation Functions in $\textrm{T}\bar{\textrm{T}}$-deformed Conformal Field Theories, arXiv:2304.14091.
  * (24) M. Guica, “$T\overline{T}$ deformations and holography.” https://indi.to/h333c.
  * (25) I. Antoniadis, S. Dimopoulos, and A. Giveon, Little string theory at a TeV, JHEP 05 (2001) 055, [hep-th/0103033].
  * (26) I. Antoniadis, A. Arvanitaki, S. Dimopoulos, and A. Giveon, Phenomenology of TeV Little String Theory from Holography, Phys. Rev. Lett. 108 (2012) 081602, [arXiv:1102.4043].
  * (27) C. Csáki, G. Lee, S. J. Lee, S. Lombardo, and O. Telem, Continuum Naturalness, JHEP 03 (2019) 142, [arXiv:1811.06019].
  * (28) E. Megías and M. Quirós, Gapped Continuum Kaluza-Klein spectrum, JHEP 08 (2019) 166, [arXiv:1905.07364].
  * (29) E. Megías and M. Quirós, The Continuum Linear Dilaton, Acta Phys. Polon. B 52 (2021) 711, [arXiv:2104.10260].
  * (30) E. Megías and M. Quirós, Analytical Green’s functions for continuum spectra, JHEP 09 (2021) 157, [arXiv:2106.09598].
  * (31) I. Antoniadis, C. Markou, and F. Rondeau, Aspects of compactification on a linear dilaton background, JHEP 09 (2021) 137, [arXiv:2106.15184].
  * (32) I. Heemskerk, J. Penedones, J. Polchinski, and J. Sully, Holography from Conformal Field Theory, JHEP 10 (2009) 079, [arXiv:0907.0151].
  * (33) A. L. Fitzpatrick, E. Katz, D. Poland, and D. Simmons-Duffin, Effective Conformal Theory and the Flat-Space Limit of AdS, JHEP 07 (2011) 023, [arXiv:1007.2412].
  * (34) S. Caron-Huot, D. Mazac, L. Rastelli, and D. Simmons-Duffin, AdS Bulk Locality from Sharp CFT Bounds, arXiv:2106.10274.
  * (35) C. W. Misner, K. S. Thorne, and J. A. Wheeler, Gravitation.  W. H. Freeman, San Francisco, 1973.
  * (36) S. S. Gubser, Curvature singularities: The Good, the bad, and the naked, Adv. Theor. Math. Phys. 4 (2000) 679–745, [hep-th/0002160].
  * (37) J. A. Cabrer, G. von Gersdorff, and M. Quirós, Soft-Wall Stabilization, New J. Phys. 12 (2010) 075012, [arXiv:0907.5361].
  * (38) S. Barbosa, “Homework on geodesics (2023).” Available on demand.
  * (39) S. Fichet, Opacity and effective field theory in anti–de Sitter backgrounds, Phys. Rev. D100 (2019), no. 9 095002, [arXiv:1905.05779].
  * (40) A. Costantino and S. Fichet, Opacity from Loops in AdS, JHEP 02 (2021) 089, [arXiv:2011.06603].
  * (41) D. Tong, “Lectures on string theory.” https://www.damtp.cam.ac.uk/user/tong/string.html.
  * (42) K. Wray, “An introduction to string theory.” https://math.berkeley.edu/~kwray/papers/string_theory.pdf.
  * (43) N. Itzhaki, J. M. Maldacena, J. Sonnenschein, and S. Yankielowicz, Supergravity and the large N limit of theories with sixteen supercharges, Phys. Rev. D 58 (1998) 046004, [hep-th/9802042].
  * (44) R. F. Streater and A. S. Wightman, PCT, spin and statistics, and all that.  1989\.
  * (45) S. Fichet, On holography in general background and the boundary effective action from AdS to dS, JHEP 07 (2022) 113, [arXiv:2112.00746].
  * (46) T. Gherghetta and B. von Harling, A Warped Model of Dark Matter, JHEP 04 (2010) 039, [arXiv:1002.2967].
  * (47) N. Arkani-Hamed, P. Benincasa, and A. Postnikov, Cosmological Polytopes and the Wavefunction of the Universe, arXiv:1709.02813.
  * (48) N. Arkani-Hamed and P. Benincasa, On the Emergence of Lorentz Invariance and Unitarity from the Scattering Facet of Cosmological Polytopes, arXiv:1811.01125.
  * (49) P. Benincasa, From the flat-space S-matrix to the Wavefunction of the Universe, arXiv:1811.02515.
  * (50) D. Baumann, W.-M. Chen, C. Duaso Pueyo, A. Joyce, H. Lee, and G. L. Pimentel, Linking the Singularities of Cosmological Correlators, arXiv:2106.05294.
  * (51) D. Baumann, C. Duaso Pueyo, A. Joyce, H. Lee, and G. L. Pimentel, The Cosmological Bootstrap: Spinning Correlators from Symmetries and Factorization, arXiv:2005.04234.
  * (52) P. Benincasa, Cosmological Polytopes and the Wavefuncton of the Universe for Light States, arXiv:1909.02517.
  * (53) E. Megías, G. Nardini, and M. Quirós, Cosmological Phase Transitions in Warped Space: Gravitational Waves and Collider Signatures, JHEP 09 (2018) 095, [arXiv:1806.04877].
  * (54) S. Fichet, E. Megías, and M. Quirós, Continuum effective field theories, gravity, and holography, Phys. Rev. D 107 (2023), no. 9 096016, [arXiv:2208.12273].
  * (55) S. Fichet, E. Megías, and M. Quirós, Cosmological dark matter from a bulk black hole, Phys. Rev. D 107 (2023), no. 11 115014, [arXiv:2212.13268].
  * (56) T. Shiromizu, K.-i. Maeda, and M. Sasaki, The Einstein equation on the 3-brane world, Phys. Rev. D 62 (2000) 024012, [gr-qc/9910076].
  * (57) U. Gursoy, E. Kiritsis, L. Mazzanti, and F. Nitti, Holography and Thermodynamics of 5D Dilaton-gravity, JHEP 05 (2009) 033, [arXiv:0812.0792].
  * (58) P. Kovtun, Lectures on hydrodynamic fluctuations in relativistic theories, J. Phys. A 45 (2012) 473001, [arXiv:1205.5040].
  * (59) S. Bhattacharyya, V. E. Hubeny, S. Minwalla, and M. Rangamani, Nonlinear Fluid Dynamics from Gravity, JHEP 02 (2008) 045, [arXiv:0712.2456].
  * (60) S. Hawking and D. N. Page, Thermodynamics of Black Holes in anti-De Sitter Space, Commun. Math. Phys. 87 (1983) 577.
  * (61) R. Hagedorn, Statistical thermodynamics of strong interactions at high-energies, Nuovo Cim. Suppl. 3 (1965) 147–186.
  * (62) P. Salomonson and B.-S. Skagerstam, On superdense superstring gases: A heretic string model approach, Nucl. Phys. B 268 (1986) 349–361.
  * (63) J. J. Atick and E. Witten, The Hagedorn Transition and the Number of Degrees of Freedom of String Theory, Nucl. Phys. B 310 (1988) 291–334.
  * (64) J. M. Maldacena, Statistical entropy of near extremal five-branes, Nucl. Phys. B 477 (1996) 168–174, [hep-th/9605016].
  * (65) J. M. Maldacena and A. Strominger, Semiclassical decay of near extremal five-branes, JHEP 12 (1997) 008, [hep-th/9710014].
  * (66) T. Harmark and N. A. Obers, Hagedorn behavior of little string theories, in International Conference on Quantization, Gauge Theory, and Strings, pp. 124–133, 6, 2000.  hep-th/0010169.
  * (67) D. Kutasov and D. A. Sahakyan, Comments on the thermodynamics of little string theory, JHEP 02 (2001) 021, [hep-th/0012258].
  * (68) T. Tanaka and Y. Himemoto, Generation of dark radiation in bulk inflaton model, Phys. Rev. D 67 (2003) 104007, [gr-qc/0301010].
  * (69) D. Langlois and L. Sorbo, Bulk gravitons from a cosmological brane, Phys. Rev. D 68 (2003) 084006, [hep-th/0306281].
  * (70) O. DeWolfe, D. Z. Freedman, S. S. Gubser, and A. Karch, Modeling the fifth-dimension with scalars and gravity, Phys. Rev. D 62 (2000) 046008, [hep-th/9909134].
  * (71) I. Papadimitriou, Multi-Trace Deformations in AdS/CFT: Exploring the Vacuum Structure of the Deformed CFT, JHEP 05 (2007) 075, [hep-th/0703152].
  * (72) E. Megías and O. Pujolas, Naturally light dilatons from nearly marginal deformations, JHEP 08 (2014) 081, [arXiv:1401.4998].
  * (73) E. Megías, H. J. Pirner, and K. Veschgini, QCD thermodynamics using five-dimensional gravity, Phys. Rev. D 83 (2011) 056003, [arXiv:1009.2953].


# FPRF: Feed-Forward Photorealistic Style Transfer of
Large-Scale 3D Neural Radiance Fields

GeonU Kim1, Kim Youwang2, Tae-Hyun Oh1,2,3

###### Abstract

We present FPRF, a feed-forward photorealistic style transfer method for
large-scale 3D neural radiance fields. FPRF stylizes large-scale 3D scenes
with arbitrary, multiple style reference images without additional
optimization while preserving multi-view appearance consistency. Prior arts
required tedious per-style/-scene optimization and were limited to small-scale
3D scenes. FPRF efficiently stylizes large-scale 3D scenes by introducing a
style-decomposed 3D neural radiance field, which inherits AdaIN’s feed-forward
stylization machinery, supporting arbitrary style reference images.
Furthermore, FPRF supports multi-reference stylization with the semantic
correspondence matching and local AdaIN, which adds diverse user control for
3D scene styles. FPRF also preserves multi-view consistency by applying
semantic matching and style transfer processes directly onto queried features
in 3D space. In experiments, we demonstrate that FPRF achieves favorable
photorealistic quality 3D scene stylization for large-scale scenes with
diverse reference images. Project page: https://kim-geonu.github.io/FPRF/

##  1 Introduction

Large-scale 3D scene reconstruction is a longstanding problem in computer
vision and graphics (Früh and Zakhor 2004; Snavely, Seitz, and Szeliski 2006;
Pollefeys et al. 2008; Agarwal et al. 2009; Zhu et al. 2018; Tancik et al.
2022), which aims to build realistic 3D virtual scenes from a set of images.
Recently, Neural Radiance Fields (Mildenhall et al. 2020; Barron et al. 2021,
2022; Fridovich-Keil et al. 2022; Jun-Seong et al. 2022; Müller et al. 2022;
Fridovich-Keil et al. 2023) and its large-scale extensions (Tancik et al.
2022; Turki, Ramanan, and Satyanarayanan 2022; Zhenxing and Xu 2022) have
shown remarkable progress in modeling coherent and photorealistic outdoor 3D
scenes, suggesting promising future directions, _e.g_., VR/AR applications. In
this work, we take a step further and focus on a task, photorealistic style
transfer (PST) for large-scale 3D scenes, _i.e_., 3D scene PST.

The 3D scene PST task aims to transfer the visual styles of style reference
images onto a large-scale 3D scene represented by a _neural radiance field_.
Within this objective, the resulting stylized output is expected to be
photorealistic and preserve the geometric structure of the original scene.
Large-scale 3D scene PST has various applications, where it can enrich virtual
3D spaces of XR applications and realistically augment existing real-world
autonomous driving datasets (Geiger, Lenz, and Urtasun 2012; Cordts et al.
2016).

Recent studies (Chen et al. 2022; Zhang et al. 2023) have developed methods
for 3D scene PST and shown plausible visual qualities. However, all of them
require additional time-consuming learning and optimization stages even after
scene reconstruction (Chen et al. 2022) or tedious per-style optimization
steps to apply even just a single style to the scene (Zhang et al. 2023). More
importantly, due to the aforementioned drawbacks, the previous 3D scene PST
methods do not scale to large 3D scenes. This motivates us to develop an
efficient PST method for large-scale 3D scenes that stylizes the whole 3D
scene without exhaustive and time-consuming per-scene or per-style
optimization.

| UPST-NeRF | StyleRF | LipRF | FPRF
---|---|---|---|---
| (arXiv2022) | (CVPR2023) | (CVPR2023) | (Ours)
Photorealistic | ✓ | ✗ | ✓ | ✓
Feed-forward | ✓ | ✓ | ✗ | ✓
Multi-reference | ✗ | ✗ | - | ✓
Single-stage training | ✗ | ✗ | ✗ | ✓
Table 1: FPRF provides a photorealistic, feed-forward style transfer method
for large-scale neural radiance fields, while supporting multiple style
reference images in the stylization stage. Our model, FPRF, differs from
competing methods, where it needs only an efficient single stage training, and
it works with arbitrary style images in a feed-forward manner.

In this work, we propose FPRF, an efficient and feed-forward PST for large-
scale 3D scenes. To implement a feed-forward PST method for a large-scale 3D
scene, we employ the adaptive instance normalization (AdaIN) method, which has
shown efficient and promising style transfer results on various tasks (Huang
and Belongie 2017; Huang et al. 2018; Gunawan et al. 2023; Wang et al. 2020;
Aberman et al. 2020; Segu et al. 2020; Huang et al. 2022; Liu et al. 2023).
Specifically, we propose a photorealistic _stylizable radiance field_
consisting of a scene _content_ field and a scene _semantic_ field. Given a
large set of photos of the target scene, we first train a grid-based scene
content field to embed the scene geometry and content features that can be
later decoded to a large-scale radiance field of arbitrary styles. The scene
semantic field is trained together to match proper local styles to the local
scene. After obtaining the scene content field, our FPRF stylizes the whole 3D
scene via AdaIN, that manipulates the scene content field with the style
reference images’ feature statistics in a feed-forward manner without any
nuisance optimization.

In addition to efficiency, stylizing a large-scale scene requires dealing with
diverse objects and contents that are hard to cover with a single reference
image. Also, it is challenging to identify a single reference that can
effectively encompass the entire semantics of a large-scale scene. Thus,
extending the existing single reference-based methods _e.g_., Chen et al.
(2022), is not straightforward, due to diverse contents in the large-scale
scene. To overcome this challenge, we introduce a style dictionary module and
style attention for efficiently retrieving the style matches of each local
part of the 3D scene from a given set of diverse style references. The
proposed style dictionary consists of pairs of a local semantic code and a
local style code extracted from the style references. To form a compact style
dictionary, we cluster similar styles and semantics and use the centroids of
the clusters as the dictionary’s elements, notably reducing the computational
complexity of the style retrieval. Using a style dictionary, we find semantic
correspondences between the local semantic codes and the style semantic field.

Our experiments demonstrate that FPRF obtains superior stylization qualities
for both large/small-scale scenes with multi-view consistent and semantically
matched style transfer. Furthermore, our model demonstrates versatility
compared to the previous methods by stylizing 3D scenes with multiple style
references, which is not feasible with other prior methods. Our main
contributions are summarized as follows:

  * •

We propose a stylizable radiance field where we can perform photorealistic
style transfer in a feed-forward manner with an efficient single-stage
training.

  * •

We propose the style dictionary and its style attention for style retrieval,
which allows us to deal with multiple style references efficiently.

  * •

To the best of our knowledge, our work is the first multi-reference based 3D
PST without any per-style optimization, which is scalable for large-scale 3D
scenes.

##  2 Related Work

Our task relates to large-scale neural scene reconstruction and photorealistic
style transfer for large-scale 3D scenes via neural feature distillation.

#### Large-scale neural 3D scene reconstruction

Realistic 3D reconstruction of large-scale scenes has been considered an
important task, which could be a stepping stone to achieve a comprehensive 3D
scene understanding and immersive virtual reality. Recently, a few seminal
studies (Tancik et al. 2022; Turki, Ramanan, and Satyanarayanan 2022; Zhenxing
and Xu 2022) tackled the task by leveraging advances in neural radiance fields
(Mildenhall et al. 2020), showing remarkable reconstruction quality for large-
scale 3D scenes.

Prior arts mainly focused on decomposing the large-scale scene into smaller
parts, _i.e_., divide-and-conquer. Block-NeRF (Tancik et al. 2022) manually
divided city-scale scenes into block-level, and Switch-NeRF (Zhenxing and Xu
2022) learns scene decomposition using a learnable gating network. Although
they can reconstruct large scenes by decomposition, they take a long time to
train and inference by using a structure composed of a large neural network
(Mildenhall et al. 2020; Barron et al. 2021). Instead of adopting time-
consuming MLP-based architecture, we leverage lightweight and easy-to-learn
K-planes (Fridovich-Keil et al. 2023) for representing large-scale 3D scenes
and build our system, FPRF. Specifically, using an efficient blockwise
decomposed K-planes representation, we learn not only the scene geometry and
radiance field, but also learn per-3D point high dimensional features for the
large-scale scene, which we call the _stylizable radiance field_. With the
stylizable radiance field and our multi-view consistent MLP color decoder,
FPRF embeds compatibility for stylizing large-scale scenes with any style
reference images while preserving the high-fidelity reconstruction quality for
the original scene even without post-optimization.

#### Photorealistic style transfer for 3D scenes

3D scene style transfer aims to stylize 3D scene according to the style of the
reference image while preserving multi-view consistency. Recently, Chiang et
al. (2022); Huang et al. (2022); Fan et al. (2022); Nguyen-Phuoc, Liu, and
Xiao (2022); Chen et al. (2022); Zhang et al. (2022); Liu et al. (2023); Zhang
et al. (2023) combine 3D neural radiance field with style transfer.

Among them, UPST-NeRF (Chen et al. 2022) and LipRF (Zhang et al. 2023) tackled
PST on 3D neural radiance field. UPST-NeRF constructs a stylizable 3D scene
with a hyper network, which is trained on stylized multi-view images of a
single scene. They can stylize a trained scene in a feed-forward manner with
arbitrary style. However, the model requires additional time-consuming
(${>}10$ hrs.) per-scene optimization after scene reconstruction. LipRF
stylizes the reconstructed 3D scene with multi-view stylized images by 2D PST
methods. They achieved 3D PST by leveraging Lipschitz network (Virmaux and
Scaman 2018) to moderate artifacts and multi-view inconsistency caused by 2D
PST methods. However, LipRF requires a time-consuming iterative optimization
procedure for every unseen reference style. One of the artistic style transfer
methods, StyleRF (Liu et al. 2023) leverages the 3D feature field to stylize
3D scenes with artistic style. They achieve feed-forward style transfer with
distilled 3D feature field, however, it requires per-scene multi-stage
training which spends more time than reconstruction (${>}5$hrs.). Our model
mitigates aforementioned inefficiency by constructing stylizable 3D radiance
field with only a single training stage spending about 1 hr. Also, our work
distinctively focuses on photorealistic stylization with the capability of
referring multi-style references, while StyleRF focuses only on artistic
stylization with a single reference. Table 1 compares the distinctiveness of
our work with the prior work.

##  3 Method

In this section, we introduce FPRF, a feed-forward Photorealistic Style
Transfer (PST) method for large-scale 3D scenes. We first introduce a single-
stage training of the stylizable radiance field using AdaIN (Sec. 3.1). We
further describe the scene semantic field for stylizing large-scale scenes
with multiple reference images (Sec. 3.2).

Figure 1: FPRF training stage. Given a set of scene images and corresponding
VGG and DINO features, FPRF learns the stylizable radiance field. Stylizable
radiance field embeds the geometry, radiance field, and semantic features of
the scene. Note that FPRF only needs the original scene images during
training, not the stylized images, while it can take arbitrary style images in
the stylization stage.

###  3.1 Large-scale Stylizable Radiance Field

Our goal is to construct a 3D large-scale radiance field that can be stylized
with reference images in a feed-forward manner while achieving photorealistic
results after stylization. For the feed-forward style transfer, we employ
adaptive instance normalization (AdaIN) (Huang and Belongie 2017), which is an
efficient style reference-based style transfer method, where it linearly
replaces the content image’s feature statistics with a given style image’s
feature as:

$\text{AdaIN}(\mathbf{F}(c),\mathbf{F}(s))=\sigma_{s}\frac{(\mathbf{F}(c)-\mu_{c})}{\sigma_{c}}+\mu_{s},$
(1)

where $\mathbf{F}(c)$ and $\mathbf{F}(s)$ are semantic features extracted from
content and style images by a pre-trained feature encoder, _e.g_., a VGG
encoder (Simonyan and Zisserman 2014). The feature statistics $\mu_{*}$ and
$\sigma_{*}$ over spatial axes are the mean and standard deviation of the
extracted features, respectively. The AdaIN layer is favorable to enable feed-
forward style transfer. This property is particularly useful for dealing with
large-scale 3D scenes and enables a fast and seamless stylization. To leverage
AdaIN’s statistic-based style transfer to the 3D scene, we propose to
reconstruct a stylizable 3D neural radiance field by distilling the 2D
features onto the field, called the stylizable radiance field.

#### Stylizable radiance field

To build a multi-view consistent stylizable feature field, we apply multi-view
bootstrapping (Simon et al. 2017) to our domain. We distill high-dimensional
features obtained from 2D input images into neural feature fields that models
the large-scale 3D scene. To represent a large-scale 3D scene, we extend
K-planes (Fridovich-Keil et al. 2023) with the block-composition manner
(Tancik et al. 2022), which is used for embedding volumetric scene geometry,
radiance, and semantic features. Specifically, we design the stylizable
radiance field with two tri-plane grids: scene _content_ field and scene
_semantic_ field. The scene semantic field embeds semantic features of a
scene, which will be discussed later in Sec. 3.2. The scene content field is
responsible for embedding accurate scene geometry and appearance-related
content features. Given a 3D scene point position $\mathbf{x}{=}(x,y,z)$ and a
ray direction vector $\mathbf{d}$ as inputs, our scene content field outputs
the density, and content feature of the query 3D point (see Fig. 1).

The original NeRF computes a pixel’s RGB color $\hat{\mathbf{C}}(\textbf{r})$
by accumulating the color $\hat{\mathbf{c}}_{i}$ and density $\sigma_{i}$ of
sampled 3D points $\mathbf{x}_{i}$ along the ray r. Correspondingly, we train
to render high-dimensional features of 3D points in the scene to a pixel value
$\hat{\mathbf{F}}(\mathbf{r})$ by accumulating features $\hat{\mathbf{f}}_{i}$
along the ray $\mathbf{r}$:

$\hat{\mathbf{F}}(\mathbf{r})=\sum^{K}_{i=1}\text{exp}\left(-\sum^{i-1}_{j=1}\sigma_{j}\delta_{j}\right)(1-\text{exp}(-\sigma_{i}\delta_{i}))\hat{\mathbf{f}}_{i},$
(2)

where $\delta_{i}$ denotes the distance between the sampled point
$\mathbf{x}_{i}$ and the next sample point,
$\text{exp}(-\sum^{i-1}_{j=1}\sigma_{j}\delta_{j})$ is a transmittance to the
point $\mathbf{x}_{i}$, and $1-\text{exp}(-\sigma_{i}\delta_{i})$ represents
the absorption by $\mathbf{x}_{i}$. We distill 2D image features to a 3D scene
by minimizing the error between the volume-rendered features and the 2D
features extracted from input images, which we call feature distillation. To
distill highly-detailed features into the 3D scenes, we use the refined 2D
features by Guided Filtering (He, Sun, and Tang 2012) before distillation.

Figure 2: FPRF stylization stage. Given the optimized stylizable radiance
field and the set of arbitrary reference images, we stylize the large-scale 3D
scene via our novel semantic-aware local AdaIN. We compose a style dictionary
consisting of local semantic codes and local style codes pairs extracted from
the clustered reference images. Using semantic features from the stylizable
radiance as a query, we find the corresponding local semantic features and
retrieve the paired local style codes. Using the retrieved semantic-style code
pairs, we perform semantic matching and local AdaIN, then finally render the
stylized colors.

#### Generalizable pre-trained MLP color decoder

The output of the scene content field requires a separate decoder to decode
the stylized feature into the color. One may naïvely train such a decoder
scene-by-scene, which suffers from a limited generalization to unseen colors
and requires additional training for stylization. In the following, we present
a scene-agnostic and pre-trained MLP color decoder $D_{\text{VGG}}$ compatible
with AdaIN. Specifically, $D_{\text{VGG}}$ transforms the distilled VGG
features into colors. To perform style transfer in a feed-forward manner, we
pre-train $D_{\text{VGG}}$ with the diverse set of content images (Lin et al.
2014) and style images (Nichol 2016), which enable $D_{\text{VGG}}$ to be
generalized to arbitrary style reference images. For that, we employ content
loss $\mathcal{L}_{c}$ and the style loss $\mathcal{L}_{s}$, similar to Huang
and Belongie (2017):
$\mathcal{L}_{D_{\text{VGG}}}=\mathcal{L}_{c}+\lambda_{s}\mathcal{L}_{s}$. The
main differences with the training process of AdaIN are threefold. First, we
use the MLP architecture instead of the CNN upsampling layer inducing multi-
view inconsistency. Also, we employ features from the shallower layer, ReLU2_1
of VGGNet, that contain richer color information. Furthermore, the features
from the input content images are upsampled to the pixel resolution for per-
pixel decoding. When training the stylizable radiance field, we fix the pre-
trained $D_{\text{VGG}}$ so that it preserves the knowledge about the
distribution of VGG features from diverse images, which induces compatibility
with AdaIN.

#### Training scene content field

We train the scene content field by optimizing the tri-plane grid features and
MLP. In detail, for the input 3D point $\mathbf{x}_{i}$ and the view direction
vector $\mathbf{d}$, the grid features of the scene content field are decoded
into the 3D point density $\sigma_{i}$ and the content feature (see the green
grid and MLP in Fig. 1). We further decode the content feature into RGB values
using the pre-trained $D_{\text{VGG}}$. At the end, we render the content
feature $\hat{\mathbf{F}}_{\text{VGG}}(\textbf{r})$ and the scene color
$\hat{\mathbf{C}}(\textbf{r})$ via volume rendering (Eq. (2)).

To perform AdaIN, we guide the content feature map
${\hat{\mathbf{F}}}_{\text{VGG}}$ to follow VGG feature distribution by
feature distillation. We distill the ground truth features
$\mathbf{F}_{\text{VGG}}(\mathbf{I})$ obtained from input images $\mathbf{I}$
via pre-trained VGGNet, by minimizing the error between
$\mathbf{F}_{\text{VGG}}(\mathbf{I})$ and the volume rendered features
${\hat{\mathbf{F}}}_{\text{VGG}}(\textbf{r})$. Note that the ground truth VGG
feature maps are upsampled to pixel resolution with guided filtering. Since
the scene content field needs to reconstruct the accurate scene geometry and
appearance, we compute the photometric loss for the volume rendered color
$\hat{\mathbf{C}}(\mathbf{r})$. Also, typical regularization losses
(Fridovich-Keil et al. 2023) are employed. The total loss function for
training the scene content field is as below:

$\mathcal{L}_{\text{content}}=\sum_{\mathbf{r}\in\mathcal{R}}\lVert\hat{\mathbf{F}}_{\text{VGG}}(\mathbf{r})-\mathbf{F}_{\text{VGG}}(\mathbf{I},\mathbf{r})\rVert^{2}_{2}\\\
+\lambda_{\text{RGB}}\sum_{\mathbf{r}\in\mathcal{R}}\lVert\hat{\mathbf{C}}(\mathbf{r})-\mathbf{C}(\mathbf{I},\mathbf{r})\rVert^{2}_{2}+\lambda_{\text{reg}}\mathcal{L}_{\text{reg}},$
(3)

where $\mathcal{R}$ is the set of sampled rays in each training batch, and
$\mathbf{F}_{\text{VGG}}(\mathbf{I},\mathbf{r})$ and
$\mathbf{C}(\mathbf{I},\mathbf{r})$ denote ground truth VGG features and RGB
values of the pixels correspond to the ray $\mathbf{r}\in\mathcal{R}$.

Note that we keep $D_{\text{VGG}}$ frozen after its pre-train stage, _i.e_.,
$D_{\text{VGG}}$ is fixed during the training stage of the scene content
field. This differs from StyleRF (Liu et al. 2023), which needs to fine-tune a
CNN-based decoder for each scene.

#### Feed-forward stylization using the scene content field

After training the scene content field, we can perform PST with an arbitrary
style image in the stylization stage. In other words, we train the scene
content field once and perform PST on a trained radiance field in a feed-
forwards manner, _i.e_., without per-style or per-scene optimization.

Given a reference image $\mathbf{I}_{s}$, we start with extracting the VGG
feature $\mathbf{F}_{\text{VGG}}(\mathbf{I}_{s})$. Then we stylize 3D content
features $\hat{\mathbf{F}}_{\text{VGG}}$ as
$\sigma_{s}\nicefrac{{(\hat{\mathbf{F}}_{\text{VGG}}-\mu_{c})}}{{\sigma_{c}}}{+}\mu_{s}$,
where $\mu_{s}$ and $\sigma_{s}$ are the mean and standard deviation of
$\mathbf{F}_{\text{VGG}}(\mathbf{I}_{s})$. By decoding the stylized content
features to RGB values using the pre-trained color decoder $D_{\text{VGG}}$,
we can render a stylized 3D scene. The mean and standard deviation of
$\hat{\mathbf{F}}_{\text{VGG}}(\mathbf{r})$ are keep tracked with the moving
average during training (Liu et al. 2023).

###  3.2 Multi-reference image 3D Scene PST via Semantic matching and Local
AdaIN

With the trained scene content field and AdaIN, we can efficiently transfer
the style of images to the 3D radiance field. However, it often fails to
produce satisfying results when it comes to large-scale 3D scenes: AdaIN only
allows a single reference image which often cannot cover all components in the
large-scale scene. To overcome this limitation, we propose a multi-reference
based 3D scene PST by semantically matching the radiance field and multiple
reference images. As shown in the Fig. 2, the process involves two steps.
First, we compose a style dictionary containing local semantic-style code
pairs obtained from semantically clustered reference images. Then, we perform
a semantic-aware style transfer by leveraging the semantic correspondence
between the 3D scene and each element of the composed style dictionary.

#### Reference image clustering

To stylize a 3D scene with multiple style reference images, we consider a set
of reference images,
$\mathcal{I}_{s}{=}\\{\mathbf{I}_{s}^{i}\\}_{i=1,\dots,N}$, where $N$ denotes
the number of reference images we use. We compose a compact style dictionary
$\mathcal{D}$ with the reference images by clustering them with similar styles
and semantics. We first extract semantic feature maps to cluster the reference
images according to semantic similarity. We employ DINO (Caron et al. 2021) as
a semantic feature encoder, which can be generalized to various domains by
being trained on large-scale datasets in a self-supervised manner. We then
apply K-means clustering to the extracted semantic feature map
$\mathbf{F}_{\text{DINO}}(\mathbf{I}_{s}^{i})$, and obtain semantically
correlated $M$ number of clusters
$\mathcal{S}{=}\\{\mathbf{S}^{ij}\\}_{i=1,\dots,N}^{j=1,\dots,M}$ from each
reference image $\mathcal{I}_{s}$.

We obtain local style codes from the clusters by extracting another feature
map $\mathbf{F}_{\text{VGG}}(\mathbf{I}_{s}^{i})$ from each reference image
with VGGNet (Simonyan and Zisserman 2014). Then we obtain the local style
code, mean $\mu_{s}^{ij}$ and standard deviation $\sigma_{s}^{ij}$, from VGG
features $\mathbf{F}_{\text{VGG}}(\mathbf{I}_{s}^{ij})\in\mathbf{S}^{ij}$
assigned to each cluster. The centroid
$\bar{\mathbf{f}}_{\text{DINO}}(\mathbf{I}_{s}^{ij})$ of each clustered
semantic feature and the assigned local style code
($\mu_{s}^{ij},\sigma_{s}^{ij}$) compose a key-value pair for the style
dictionary $\mathcal{D}$, as
$\mathcal{D}_{ij}{=}\\{\bar{\mathbf{f}}_{\text{DINO}}(\mathbf{I}_{s}^{ij}){:}(\mu_{s}^{ij},\sigma_{s}^{ij})\\}_{i=1,\dots,N}^{j=1,\dots,M}$.
With this compact style dictionary, we can efficiently perform local style
transfer using multiple reference images by semantically matching the clusters
with the 3D scene.

#### Scene semantic field

To semantically match the 3D scene and the reference image clusters, we design
and learn an auxiliary 3D feature grid, called scene semantic field. The scene
semantic field contains semantic features of the 3D scene (Kobayashi,
Matsumoto, and Sitzmann 2022; Tschernezki et al. 2022; Kerr et al. 2023). To
distill semantic features to the scene semantic field, we optimize the tri-
plane features and MLP (orange grid and MLP in Fig. 1) by minimizing the error
between rendered features $\hat{F}_{\text{DINO}}(\mathbf{r})$ and features
extracted from the input images by DINO as follows:

$\mathcal{L}_{\text{semantic}}=\sum_{\mathbf{r}\in\mathcal{R}}\lVert\hat{\mathbf{F}}_{\text{DINO}}(\mathbf{r})-\mathbf{F}_{\text{DINO}}(\mathbf{I},\mathbf{r})\rVert_{1},$
(4)

where $\mathbf{F}_{\text{DINO}}(\mathbf{I},\mathbf{r})$ denotes ground truth
DINO features matched to ray $\mathbf{r}$. The density $\sigma$ from the scene
content field is used for volume rendering, and
$\mathcal{L}_{\text{semantic}}$ does not affect the learning of the density.
We do not query view direction as input, in order to preserve multi-view
semantic consistency. Also, for constructing a fine-grained scene semantic
field, the ground truth DINO feature maps are refined by guided filtering (He,
Sun, and Tang 2012). The guided filtering enables consistent distillation of
semantic features, resulting in clean and photorealistic stylized outputs (see
Fig. 3).

Figure 3: Effects of guided filtering on semantic features. [Top] Given the
trained 3D scene and the reference image (left), we visualize the learned
stylizable radiance field without (mid) / with (right) guided filtering. The
learned semantic features are much sharper when guided filtering is applied.
[Bottom] The stylizable radiance field shows degraded stylization results if
learned without guided filtering, _e.g_., blurry boundaries (left), higher
stylization quality when learned with guided filtering (right).

#### Semantic correspondence matching & Local AdaIN

When rendering the stylized 3D scene, we use two semantic feature matrices for
computing semantic correspondence between the 3D scene and the elements of the
style dictionary $\mathcal{D}$. The first one is
$\hat{\mathbf{F}}_{\text{DINO}}\in\mathbb{R}^{K\times C_{D}}$, obtained from
the scene semantic field, where $K$ is the number of queried 3D points, and
$C_{D}$ is the channel size of the semantic feature, _i.e_., DINO feature. The
other one is
$\bar{\mathbf{F}}_{\text{DINO}}(\mathbf{I}_{s})\in\mathbb{R}^{T\times C_{D}}$
comprising keys $\bar{\mathbf{F}}_{\text{DINO}}(\mathbf{I}_{s}^{ij})$ of
$\mathcal{D}$, which are the centroids of the $T$ clusters. Given semantic
feature matrices, $\hat{\mathbf{F}}_{\text{DINO}}$ and
$\bar{\mathbf{F}}_{\text{DINO}}(\mathbf{I}_{s})$, we compute a cross-
correlation matrix $\mathbf{R}$ as:

$\mathbf{R}=\hat{\mathbf{F}}_{\text{DINO}}\,\bar{\mathbf{F}}_{\text{DINO}}(\mathbf{I}_{s})^{\top}.$
(5)

For mapping local styles of the reference images according to R, we compose
two matrices,
$\textbf{M}(\mathbf{F}_{\text{VGG}}(\mathbf{I}_{s}))\in\mathbb{R}^{T\times
C_{V}}$ and
$\mathbf{\Sigma}(\mathbf{F}_{\text{VGG}}(\mathbf{I}_{s}))\in\mathbb{R}^{T\times
C_{V}}$, comprising of the local style codes ($\mu_{s}^{ij}$,
$\sigma_{s}^{ij}$) from the style dictionary, where $C_{V}$ denotes the
channel size of VGG feature map. We compute the matrix form of semantic-
weighted style codes $(\textbf{M}_{w},\mathbf{\Sigma}_{w})$ as follows:

$\begin{gathered}\textbf{M}_{w}=\mathbf{R}^{\texttt{S}}\textbf{M}(\mathbf{F}_{\text{VGG}}(\mathbf{I}_{s}))\\\
\mathbf{\Sigma}_{w}=\mathbf{R}^{\texttt{S}}\mathbf{\Sigma}(\mathbf{F}_{\text{VGG}}(\mathbf{I}_{s})),\end{gathered}$
(6)

where $\mathbf{R}^{\texttt{S}}=\texttt{Softmax}(\mathbf{R})$ demonstrates
style attention assigned to the queried 3D point features. The semantic-
weighted style code ($\textbf{M}_{w}$, $\mathbf{\Sigma}_{w}$) are assigned to
each 3D point according to the style attention. We feed these semantic-
weighted style codes to AdaIN layer as
$\mathbf{\Sigma}_{w}\nicefrac{{(\hat{\mathbf{F}}_{\text{VGG}}-\mu_{c})}}{{\sigma_{c}}}+\textbf{M}_{w}$,
and perform volumetric rendering to obtain final stylized scene renderings.
Note that this semantic-aware local AdaIN preserves the multi-view stylized
color consistency by directly measuring semantic correspondence between
reference images and features on the scene semantic fields (Kobayashi,
Matsumoto, and Sitzmann 2022; Kerr et al. 2023).

Figure 4:  Multi-view appearance consistency on the San Francisco Mission Bay
dataset (Tancik et al. 2022). FPRF preserves multi-view appearance consistency
even in extreme viewpoint change, while 2D PST methods (Wu et al. (2022); Chiu
and Gurari (2022)) produce inconsistent colors of the same building as the
viewpoint changes.

Figure 5: PST quality comparison on the LLFF dataset (Mildenhall et al. 2019).
Compared to the competing 3D PST methods, FPRF stylizes the radiance field in
a photorealistic manner by transferring the diverse color of the reference
image while preserving the original images’ naturalness and vividness. .

We found that computing $\textbf{M}_{w}$ and $\mathbf{\Sigma}_{w}$ on the
feature map resolution without clustering (Gunawan et al. 2023) is inefficient
for the volume rendering framework where iterative rendering of rays is
inevitable. Our clustering enables efficient style transfer, especially for
cases using multiple reference images. We highlight that photorealistic scene
stylization results are obtained when ${\sim}10$ clusters are used. It is
worth noting that the clustering process takes no more than 1 _sec._ for each
reference image. Using the small number of clusters allows us to avoid
iterative concatenation of high-dimensional reference image features and
effectively reduces the computational cost of matrix multiplication.

##  4 Experiments

In this section, we demonstrate the qualitative results of FPRF on large- and
small-scale scenes, and ablation studies.

Figure 6: Multi-reference style transfer. FPRF stylizes the 3D radiance field
with multiple reference images. Each heatmap shows the similarity between the
semantic features of a highlighted patch and the reference image. Our model
comprehends the semantic relationship of a large-scale 3D scene and matches
the scene with the reference images.

#### PST on large-scale scenes

For large-scale scenes, we consider the San Francisco Mission Bay dataset
(Tancik et al. 2022), a city scene dataset consisting of about 12,000 images
recorded by 12 cameras. Since we propose the first method aiming for large-
scale 3D scene PST, no 3D PST method supports large-scale datasets. Therefore,
we compare FPRF against two competing 2D PST methods, CCPL (Wu et al. 2022)
and $\text{PhotoWCT}^{2}$ (Chiu and Gurari 2022). Figure 5 illustrates a
qualitative comparison on large-scale scenes. We observe that 2D PST methods
fail to preserve multi-view color consistency under wide-range view changes,
_e.g_., they obtain different colors of the same building and sky as the
viewpoints change. Also, they stylize images without understanding of semantic
relation between the content image and the reference image. Instead, our FPRF
elaborately transfers styles by reflecting the semantic correspondence between
scene and reference images. Semantic matching can also preserve multi-view
consistency by directly measuring semantic correspondence between reference
images and 3D points in the 3D scene semantic field directly.

Figure 7: Ablation studies for the VGG feature distillation loss and the pre-
trained color decoder. “w/o $\mathcal{L}_{\text{VGG}}$” trains model without
the VGG feature distillation loss $\mathcal{L}_{\text{VGG}}$. “w/o
$D_{\text{VGG}}$” replaces the pre-trained color decoder $D_{\text{VGG}}$ to
an MLP which is trained from scratch during scene optimization.

#### PST on small-scale scenes

For small-scale scenes, we consider LLFF (Mildenhall et al. 2019), which
includes eight real forward-facing scenes. We compare our model with two
competing 3D PST methods; LipRF (Zhang et al. 2023), UPST-NeRF (Chen et al.
2022), and the most recent feed-forward 3D _artistic_ style transfer method,
StyleRF (Liu et al. 2023). As shown in Fig. 5, our method transfers the
diverse colors of the style reference image well while maintaining the texture
fidelity of the original scene. While UPST-NeRF effectively retains the
structure of the scene, the stylized scene’s color style differs from the
reference. LipRF stabilizes the artifacts caused by 2D PST methods with the
Lipschitz network, but it tends to oversmooth the scene and loses the color
diversity of the reference image. Noticeably, StyleRF fails to obtain
photorealistic results and loses the detailed structure of the original scene.
Note that UPST-NeRF and StyleRF require per-scene optimization after scene
reconstruction for style transfer, and LipRF needs per-style optimization. On
the contrary, our model achieves feed-forward PST after an efficient single-
stage learning of the stylizable radiance field.

#### Multi-reference style transfer

Figure 6 shows the style transfer result using multiple reference images. Our
model effectively selects suitable styles from multiple references with scene
semantic field. Semantic similarity is computed by multiplying features from
the scene semantic field with DINO (Caron et al. 2021) feature maps extracted
from reference images. The similarity map clearly shows that our model
comprehends the accurate semantic relationship between scenes and reference
images.

#### Ablation studies

Figure 7 shows the effects of the VGG feature distillation loss and the pre-
trianed color decoder. The VGG feature distillation loss helps preserve the
original scene content and improve the quality of style transfer, by guiding
the content feature to follow VGG feature distribution. The generalizability
of the pre-trained color decoder allows the model to get arbitrary style
reference images as input.

##  5 Conclusion

In this paper, we present FPRF, a novel stylizable 3D radiance field aiming
large-scale 3D scene photorealistic style transfer (PST). FPRF allows feed-
forward PST after only a single-stage training by leveraging AdaIN. FPRF also
supports multi-reference style transfer, which allows stylizing large-scale 3D
scenes which consist of diverse components.

The current limitation is that the semantic matching performance of our model
is bounded by the capability of the semantic image encoder, DINO. Nonetheless,
since our model can utilize any semantic encoder for constructing the scene
semantic field, the performance of our model stands to benefit from the
emergence of more advanced models.

## Acknowledgments

This work was supported by the LG Display (2022008004), Institute of
Information & communications Technology Planning & Evaluation (IITP) grant
funded by the Korea government(MSIT) (No.2022-0-00124, Development of
Artificial Intelligence Technology for Self-Improving Competency-Aware
Learning Capabilities; No. RS-2022-00164860, Development of human digital twin
technology based on dynamic behavior modeling and human-object-space
interaction; No.2021-0-02068, Artificial Intelligence Innovation Hub; No.
2019-0-01906, Artificial Intelligence Graduate School Program(POSTECH)), and
National Research Foundation of Korea (NRF) grant funded by the Korea
government (MSIT) (No. NRF-2021R1C1C1006799).

## References

  * Aberman et al. (2020) Aberman, K.; Weng, Y.; Lischinski, D.; Cohen-Or, D.; and Chen, B. 2020.  Unpaired motion style transfer from video to animation.  _ACM Transactions on Graphics (TOG)_ , 39(4): 64–1.
  * Agarwal et al. (2009) Agarwal, S.; Snavely, N.; Simon, I.; Seitz, S. M.; and Szeliski, R. 2009.  Building Rome in a day.  In _IEEE International Conference on Computer Vision (ICCV)_.
  * Barron et al. (2021) Barron, J. T.; Mildenhall, B.; Tancik, M.; Hedman, P.; Martin-Brualla, R.; and Srinivasan, P. P. 2021.  Mip-nerf: A multiscale representation for anti-aliasing neural radiance fields.  In _IEEE International Conference on Computer Vision (ICCV)_ , 5855–5864.
  * Barron et al. (2022) Barron, J. T.; Mildenhall, B.; Verbin, D.; Srinivasan, P. P.; and Hedman, P. 2022.  Mip-nerf 360: Unbounded anti-aliased neural radiance fields.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 5470–5479.
  * Caron et al. (2021) Caron, M.; Touvron, H.; Misra, I.; Jégou, H.; Mairal, J.; Bojanowski, P.; and Joulin, A. 2021.  Emerging properties in self-supervised vision transformers.  In _IEEE International Conference on Computer Vision (ICCV)_.
  * Chen et al. (2022) Chen, Y.; Yuan, Q.; Li, Z.; Xie, Y. L. W. W. C.; Wen, X.; and Yu, Q. 2022.  Upst-nerf: Universal photorealistic style transfer of neural radiance fields for 3d scene.  _arXiv preprint arXiv:2208.07059_.
  * Chiang et al. (2022) Chiang, P.-Z.; Tsai, M.-S.; Tseng, H.-Y.; Lai, W.-S.; and Chiu, W.-C. 2022.  Stylizing 3d scene via implicit representation and hypernetwork.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 1475–1484.
  * Chiu and Gurari (2022) Chiu, T.-Y.; and Gurari, D. 2022.  Photowct2: Compact autoencoder for photorealistic style transfer resulting from blockwise training and skip connections of high-frequency residuals.  In _IEEE Winter Conf. on Applications of Computer Vision (WACV)_.
  * Cordts et al. (2016) Cordts, M.; Omran, M.; Ramos, S.; Rehfeld, T.; Enzweiler, M.; Benenson, R.; Franke, U.; Roth, S.; and Schiele, B. 2016.  The Cityscapes Dataset for Semantic Urban Scene Understanding.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Fan et al. (2022) Fan, Z.; Jiang, Y.; Wang, P.; Gong, X.; Xu, D.; and Wang, Z. 2022.  Unified implicit neural stylization.  In _European Conference on Computer Vision_ , 636–654. Springer.
  * Fridovich-Keil et al. (2023) Fridovich-Keil, S.; Meanti, G.; Warburg, F. R.; Recht, B.; and Kanazawa, A. 2023.  K-Planes: Explicit Radiance Fields in Space, Time, and Appearance.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Fridovich-Keil et al. (2022) Fridovich-Keil, S.; Yu, A.; Tancik, M.; Chen, Q.; Recht, B.; and Kanazawa, A. 2022.  Plenoxels: Radiance fields without neural networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 5501–5510.
  * Früh and Zakhor (2004) Früh, C.; and Zakhor, A. 2004.  An automated method for large-scale, ground-based city model acquisition.  _International Journal of Computer Vision_ , 60: 5–24.
  * Geiger, Lenz, and Urtasun (2012) Geiger, A.; Lenz, P.; and Urtasun, R. 2012.  Are we ready for Autonomous Driving? The KITTI Vision Benchmark Suite.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Gunawan et al. (2023) Gunawan, A.; Kim, S. Y.; Sim, H.; Lee, J.-H.; and Kim, M. 2023.  Modernizing Old Photos Using Multiple References via Photorealistic Style Transfer.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 12460–12469.
  * He, Sun, and Tang (2012) He, K.; Sun, J.; and Tang, X. 2012.  Guided image filtering.  _IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI)_ , 35(6): 1397–1409.
  * Huang and Belongie (2017) Huang, X.; and Belongie, S. 2017.  Arbitrary Style Transfer in Real-time with Adaptive Instance Normalization.  In _IEEE International Conference on Computer Vision (ICCV)_.
  * Huang et al. (2018) Huang, X.; Liu, M.-Y.; Belongie, S.; and Kautz, J. 2018.  Multimodal unsupervised image-to-image translation.  In _Proceedings of the European conference on computer vision (ECCV)_ , 172–189.
  * Huang et al. (2022) Huang, Y.-H.; He, Y.; Yuan, Y.-J.; Lai, Y.-K.; and Gao, L. 2022.  Stylizednerf: consistent 3d scene stylization as stylized nerf via 2d-3d mutual learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 18342–18352.
  * Jun-Seong et al. (2022) Jun-Seong, K.; Yu-Ji, K.; Ye-Bin, M.; and Oh, T.-H. 2022.  Hdr-plenoxels: Self-calibrating high dynamic range radiance fields.  In _European Conference on Computer Vision_ , 384–401. Springer.
  * Kerr et al. (2023) Kerr, J.; Kim, C. M.; Goldberg, K.; Kanazawa, A.; and Tancik, M. 2023.  Lerf: Language embedded radiance fields.  In _IEEE International Conference on Computer Vision (ICCV)_.
  * Kobayashi, Matsumoto, and Sitzmann (2022) Kobayashi, S.; Matsumoto, E.; and Sitzmann, V. 2022.  Decomposing nerf for editing via feature field distillation.  In _Advances in Neural Information Processing Systems (NeurIPS)_.
  * Lin et al. (2014) Lin, T.-Y.; Maire, M.; Belongie, S.; Hays, J.; Perona, P.; Ramanan, D.; Dollár, P.; and Zitnick, C. L. 2014.  Microsoft coco: Common objects in context.  In _Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13_ , 740–755. Springer.
  * Liu et al. (2023) Liu, K.; Zhan, F.; Chen, Y.; Zhang, J.; Yu, Y.; El Saddik, A.; Lu, S.; and Xing, E. P. 2023.  StyleRF: Zero-shot 3D Style Transfer of Neural Radiance Fields.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 8338–8348.
  * Mildenhall et al. (2019) Mildenhall, B.; Srinivasan, P. P.; Ortiz-Cayon, R.; Kalantari, N. K.; Ramamoorthi, R.; Ng, R.; and Kar, A. 2019.  Local light field fusion: Practical view synthesis with prescriptive sampling guidelines.  _ACM Transactions on Graphics (TOG)_ , 38(4): 1–14.
  * Mildenhall et al. (2020) Mildenhall, B.; Srinivasan, P. P.; Tancik, M.; Barron, J. T.; Ramamoorthi, R.; and Ng, R. 2020.  NeRF: Representing Scenes as Neural Radiance Fields for View Synthesis.  In _European Conference on Computer Vision (ECCV)_.
  * Müller et al. (2022) Müller, T.; Evans, A.; Schied, C.; and Keller, A. 2022.  Instant neural graphics primitives with a multiresolution hash encoding.  _ACM Transactions on Graphics (ToG)_ , 41(4): 1–15.
  * Nguyen-Phuoc, Liu, and Xiao (2022) Nguyen-Phuoc, T.; Liu, F.; and Xiao, L. 2022.  Snerf: stylized neural implicit representations for 3d scenes.  _arXiv preprint arXiv:2207.02363_.
  * Nichol (2016) Nichol, K. 2016.  Painter by numbers, Wikiart, 2016.  _URL https://www. kaggle. com/c/painter-by-numbers/overview_.
  * Pollefeys et al. (2008) Pollefeys, M.; Nistér, D.; Frahm, J.-M.; Akbarzadeh, A.; Mordohai, P.; Clipp, B.; Engels, C.; Gallup, D.; Kim, S.-J.; Merrell, P.; et al. 2008.  Detailed real-time urban 3d reconstruction from video.  _International Journal of Computer Vision_ , 78: 143–167.
  * Segu et al. (2020) Segu, M.; Grinvald, M.; Siegwart, R.; and Tombari, F. 2020.  3dsnet: Unsupervised shape-to-shape 3d style transfer.  _arXiv preprint arXiv:2011.13388_.
  * Simon et al. (2017) Simon, T.; Joo, H.; Matthews, I.; and Sheikh, Y. 2017.  Hand keypoint detection in single images using multiview bootstrapping.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Simonyan and Zisserman (2014) Simonyan, K.; and Zisserman, A. 2014.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_.
  * Snavely, Seitz, and Szeliski (2006) Snavely, N.; Seitz, S. M.; and Szeliski, R. 2006.  Photo tourism: Exploring photo collections in 3D.  In _SIGGRAPH Conference Proceedings_.
  * Tancik et al. (2022) Tancik, M.; Casser, V.; Yan, X.; Pradhan, S.; Mildenhall, B.; Srinivasan, P.; Barron, J. T.; and Kretzschmar, H. 2022.  Block-NeRF: Scalable Large Scene Neural View Synthesis.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Tschernezki et al. (2022) Tschernezki, V.; Laina, I.; Larlus, D.; and Vedaldi, A. 2022.  Neural Feature Fusion Fields: 3D distillation of self-supervised 2D image representations.  In _International Conference on 3D Vision (3DV)_ , 443–453. IEEE.
  * Turki, Ramanan, and Satyanarayanan (2022) Turki, H.; Ramanan, D.; and Satyanarayanan, M. 2022.  Mega-nerf: Scalable construction of large-scale nerfs for virtual fly-throughs.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 12922–12931.
  * Virmaux and Scaman (2018) Virmaux, A.; and Scaman, K. 2018.  Lipschitz regularity of deep neural networks: analysis and efficient estimation.  _Advances in Neural Information Processing Systems_ , 31.
  * Wang et al. (2020) Wang, J.; Wen, C.; Fu, Y.; Lin, H.; Zou, T.; Xue, X.; and Zhang, Y. 2020.  Neural Pose Transfer by Spatially Adaptive Instance Normalization.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Wu et al. (2022) Wu, Z.; Zhu, Z.; Du, J.; and Bai, X. 2022.  CCPL: contrastive coherence preserving loss for versatile style transfer.  In _European Conference on Computer Vision_ , 189–206. Springer.
  * Zhang et al. (2022) Zhang, K.; Kolkin, N.; Bi, S.; Luan, F.; Xu, Z.; Shechtman, E.; and Snavely, N. 2022.  Arf: Artistic radiance fields.  In _European Conference on Computer Vision_ , 717–733. Springer.
  * Zhang et al. (2023) Zhang, Z.; Liu, Y.; Han, C.; Pan, Y.; Guo, T.; and Yao, T. 2023.  Transforming Radiance Field with Lipschitz Network for Photorealistic 3D Scene Stylization.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 20712–20721.
  * Zhenxing and Xu (2022) Zhenxing, M.; and Xu, D. 2022.  Switch-NeRF: Learning Scene Decomposition with Mixture of Experts for Large-scale Neural Radiance Fields.  In _International Conference on Learning Representations (ICLR)_.
  * Zhu et al. (2018) Zhu, S.; Zhang, R.; Zhou, L.; Shen, T.; Fang, T.; Tan, P.; and Quan, L. 2018.  Very large-scale global sfm by distributed motion averaging.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 4568–4577.