# Comprehending Variability in Analysis Results of Software Product Lines

Rafael F. Toledo Joanne M. Atlee Rui Ming Xiong  rftoledo, jmatlee,
<EMAIL_ADDRESS>University of WaterlooCanada

###### Abstract.

Analyses of a software product line (SPL) typically report variable results
that are annotated with logical expressions indicating the set of product
variants for which the results hold. These expressions can get complicated and
difficult to reason about when the SPL has lots of features and product
variants. Previous work introduced a visualizer that supports filters for
highlighting the analysis results that apply to product variants of interest,
but this work was weakly evaluated. In this paper, we report on a controlled
user study that evaluates the effectiveness of this new visualizer in helping
the user search variable results and compare the results of multiple variants.
Our findings indicate that the use of the new visualizer significantly
improves the correctness and efficiency of the user’s work and reduces the
user’s cognitive load in working with variable results.

††conference: ; ; ††copyright: none

##  1\. Introduction

Developers pose software queries in their efforts to understand the behaviour
of large, complex software systems (latoza2010developers, ; sillito2008asking,
). It is well known that such queries can be difficult and time-consuming, and
several researchers have investigated tools to ease both the asking of such
questions and the understanding of the query results (barnett2014get, ;
latoza2011, ; yoo2022investigating, ).

These challenges become even more difficult when the software in question is a
software product line (SPL). An SPL represents a family of related software
product variants and is typically structured as a collection of mandatory and
optional features (Clements:2001, ); product variants are distinguished by the
set of optional features they include. Thus, applying software queries to an
SPL produces variable results: many query results will apply to some product
variants and not to others (e.g., if the query refers to feature-specific
code).

The typical approach to representing variable analysis results is to annotate
each result with a presence condition (PC), where the PC represents the
product variants for which the result holds (spllift-PC, ; ModelChecking-PC, ;
TypeSafety-PC, ; Analysis-PC, ; ModelChecking-PC2, ; shahin2023applying, ). A
PC is a propositional formula over Boolean feature variables, whose values
denote whether their respective features are present ($true$) or not ($false$)
in the PC’s variants. Reasoning about variable analysis results is more
demanding than simply matching PC expressions. If an engineer is interested in
results pertaining to particular variants of concern (e.g., variants
$(F\wedge!G)\\!\vee\\!H)$), the engineer needs to ascertain which of the many
results have PC annotations that overlap with the variants of concern (i.e.,
which conjunctions of PCs and the variants-of-concern expression are
satisfiable).

Recently, Shahin et al. (shahin2023applying, ) presented enhancements to the
Neo4j Browser (Neo4j, ) to not only annotate variable query results with their
respective PCs but also provide support for highlighting results whose PCs
overlap with a provided filter (also specified as a PC). The engineer can
create multiple filters, assign each filter a different colour, and the
browser will highlight each query result whose PC has at least one variant in
common with the filters. The enhanced browser looks promising in helping
engineers to search and explore variable analysis results and compare the
results of multiple variants, but the work has only been semi-formally
evaluated by a small user study involving six engineers who commented on the
perceived utility of images from the browser (shahin2023applying, ).

We obtained the enhanced Neo4j Browser (shahin2023applying, ) from its authors
and conducted a controlled user experiment to assess its effectiveness helping
users reasoning about variable results from analyses of a software product
line. Our study involved 42 student participants and found that the
participants who used filters to highlight variant-specific results exhibited
statistically significant improvements in the correctness and efficiency of
their work and reported significantly lower levels of expended mental effort.
A high majority of all participants reported a strong preference for such
coloured filters, but lower-level visualization options of how variable
results are coloured had no significant impact on performance. Although we
evaluated only the enhanced Neo4j Browser, we expect that the visualizations
and our study’s findings would be applicable to other graph-based analyses and
visualizers (latoza2011, ; yoo2022investigating, ) when applied to SPLs.

The rest of this paper is organized as follows. Section 2 provides an overview
of software product lines, analysis of SPLs, and the visualizer
(shahin2023applying, ) being evaluated in this paper. Section 3 describes the
design of our user study and we report the study results in Section 4. We
conclude with a discussion of our take aways from the study and thoughts on
potential directions for future work.

##  2\. Preliminaries

In this section, we overview fundamental concepts of software product lines
(SPLs), analyses of SPLs, and the enhanced Neo4j Browser (shahin2023applying,
) used to visualize the variable results of SPL analyses.

###  2.1. Software Product Lines

A _software product line (SPL)_ is a family of related software products or
variants that is typically structured as a collection of mandatory and
optional features (e.g., cellphones, automotive software) (Clements:2001, ).
An SPL’s variants are differentiated by their optional features. The number of
an SPL’s variants can be exponential in the number of its optional features,
but constraints among features typically preclude all possible feature
combinations from being valid variants.

Consider a graph product line (GPL) (based on Lopez-Herrejon et al.
(lopez2001standard, )). The product line includes features implementing types
of graphs (i.e., Directed, Undirected, Weighted), search algorithms (i.e.,
breadth-first search (BFS) and depth-first search (DFS)), and other common
graph algorithms (Cycle checking, Connected Components (CC), and Prim’s
algorithm for minimum spanning tree). A feature model (Kang:1990, ) (in Figure
1) shows the GPL’s features and feature constraints. The root node represents
the full GPL and other nodes represent mandatory (black dot) and optional
(white dot) features. The arcs underneath a node represent feature constraints
between the node and its child nodes: if the node is in a variant, then a
black arc indicates at least one child node must also be included in the
variant and a white arc indicates exactly one child node must be included in
the variant. Thus a GPL variant must include at least one graph algorithm and
exactly one search algorithm. The feature model also includes textual cross-
tree constraints (shown in the bottom-left corner) that define constraints
among features that are not directly related in the model’s tree structure. A
“requires" constraint expresses a feature dependency and an “excludes"
constraint expresses mutual exclusion.

Figure 1. Feature model of a reduced version of GPL (lopez2001standard, ).

⬇

1void GraphApp::BFS(int srcID) {

2 …

3 if (Weighted) {

4 …

5 targetID = edge->getTargetID();

6

7 if (Undirected) {

8 …

9 srcID = edge->getSrcID();

10 }

11 }

12

13 if (!Weighted){

14 for (int neighborID :

15 nodes[currentNodeID]->getNgbrs()) {

16 …

17 }

18 }

19…

(a) Function BFS.

(b) Dataflows in function BFS.

Figure 2. Code and dataflows annotated with PCs

In an _annotative_ SPL (Thum:2014, ), feature-specific code is encapsulated in
conditional statements that are guarded (annotated) with feature expressions.
Each feature is represented by a Boolean constant (called a _feature
variable_), and _feature expressions_ are Boolean expressions over the feature
variables. For example, Figure 2a shows snippets of the GPL’s configurable BFS
algorithm. The values of feature variables $Weighted$ and $Undirected$ (_true_
or _false_) indicate whether their corresponding features are present or
absent in a GPL variant. Lines 4-10 are specific to variants in which the
feature $Weighted$ is present; lines 8-9 are specific to variants in which
features $Weighted$ and $Undirected$ are both present; and lines 14-17 are
specific only to variants in which feature $Weighted$ is absent.

Variants can be represented by _presence conditions (PCs)_ , where a PC is a
propositional formula over the feature variables111We use the syntax $!$,
$\wedge$, $\vee$ for the propositional operators $not$, $and$, $or$,
respectively.. A PC can represent a single variant or a set of variants. Thus
in the GPL, the PC Weighted represents all variants that include weighted
graphs, and the PC $true$ represents all the GPL’s variants.

###  2.2. SPL Analysis and Visualization

Several program analyses have been lifted to enable efficient analyses of SPLs
(spllift-PC, ; ModelChecking-PC, ; TypeSafety-PC, ; Analysis-PC, ;
ModelChecking-PC2, ; shahin2023applying, ). Such analyses are called
variability-aware analyses, and they report results annotated with PCs
representing the variants for which the results hold. For example, the
variability-aware analysis employed in Shahin et al. (shahin2023applying, ) is
a lifted Datalog engine. Because the Datalog engine is lifted, rather than a
specific query, this work supports any analysis that can be encoded as a
Datalog query, including reachability analyses about control- and data-flows
(shahin2023applying, ), pointer and taint analyses (ShahinTSE, ), and def-use
analysis (datalog-defuse, ). To enable analysis of large, heterogenous SPLs,
this approach analyzes a factbase model comprising a collection of program
facts extracted from the SPL’s source code. Program facts include entities
(e.g., functions, variables, components, control blocks), relationships
between entities (e.g., function calls, variable assignments, containment,
consecutive control blocks), and attributes of entities and relationships
(e.g., names, PCs). Facts can be extracted from multiple types of artifacts
written in different languages (davis2010whence, ; CPPX, ;
bravenboer2009strictly, ; muscedere2019detecting, ), and factbase analyses
typically scale better than code analyses.

Consider again the code snippets in Figure 2(a). The variable assignment to
targetID (line 5) is in variants $Weighted$, the assignment to srcID (line 9)
in in variants $Weighted\wedge\\!Undirected$, and the assignment to neighborID
(line 14) is in variants $!Weighted$. Figure 2(b) shows an annotated graphical
model representing these program facts and their presence conditions. If an
engineer wants to find dataflows in weighted, undirected variants of the GPL,
they need to check that a dataflow’s PC is satisfiable when the features
$Weighted$ and $Undirected$ are enabled. In this example, the write facts
involving targetID and srcID hold in the variants of interest.

Shahin et al. (shahin2023applying, ) introduces a graph-based interface that
not only visualizes PC-annotated results of variability-aware factbase
analyses, but also provides facilities to highlight results that are relevant
to the engineer. The user types the PCs of the variants of interest into a
textbox in the top-left corner of the interface and clicks the green button to
create a filter. The interface then colours the model elements whose PCs have
at least one variant in common with the filter’s PC. Figure 3 shows the result
of applying a filter to the dataflows visualized in Figure 2(b).

Figure 3. Highlighted BFS dataflows in variants of interest

The engineer can create multiple filters to compare variants and can customize
the colour of each filter’s highlights. They can also customize how highlights
from multiple filters are visualized: (a) Arrow segments, (b) Arrow stripes,
(c) Separate Arrows, and (d) Arrow shapes. Figures 4a-d show examples of these
four options.

The interface is a promising approach for visualizing the results of
variability-aware analyses but its usability has been weakly evaluated. Shahin
et al. (shahin2023applying, ) conducted an unobserved experiment with six
engineers that assessed the engineers’ impressions of images from the
interface. To address this weakness, we conducted an observed experiment to
measure and assess the experience of many more participants who used the
visualizer’s features to understand and reason about variability-aware
analysis results.

(a) Arrow segments

(b) Arrow stripes

(c) Separate arrows

(d) Arrows shapes

Figure 4. Highlight visualization options

##  3\. Experimental Design

Our evaluation of the enhanced Neo4j Browser considers multiple aspects of the
user’s experience. Our primary goal was to assess hypotheses about gains in
time, correctness, and cognitive load that the visualization features might
provide and whether the filter customization options would affect any measured
gains. We also wanted to understand how the users feel about the interface.

We obtained a copy of the interface from the authors of (shahin2023applying, )
and designed a controlled user study that compares the original Neo4j Browser
(Neo4jBrowser, ) and the variability-aware visualizer presented in
(shahin2023applying, ) with respect to the following null hypotheses.

  1. H1

Efficiency: Using coloured filters does not change the amount of time it takes
to comprehend variability-aware analysis results.

  2. H2

Correctness: Using coloured filters does not change the number of mistakes
made when comprehending variability-aware analysis results.

  3. H3

Cognitive load: Using coloured filters does not change the cognitive load of
performing comprehension tasks involving variability-aware analysis results.

  4. H4

User preference: Users feel indifferent about using coloured filters to
highlight variability-aware analysis results.

  5. H5

Filter Visualization Options: The filters visualization options have the same
impact on user efficiency and correctness.

Study sessions were held online during one-on-one video calls between each
participant and the researcher. Participants accessed the study materials
(tools, tasks, survey) via a web browser on their computer (i.e., laptop or
desktop), and they shared their screen with the researcher.

Figure 5. Graphical model of the results from a variability-aware control-flow
analysis of GPL function execComnd.

⬇

Which function(s) may be directly called by the function execComnd in the
following program variant V1?

V1: kWeighted /\ kUndirected /\ kDFS /\ !kBFS /\ kCycle /\ kConnectedComps /\
!kPrim

(a) Task example for identifying facts belonging to a single variant.

⬇

Which function(s) may be directly called by the function execComnd in the
program variant V2 but not in V1?

V1: kWeighted /\ kUndirected /\ kDFS /\ !kBFS /\ kCycle /\ kConnectedComps /\
!kPrim

V2: kWeighted /\ kUndirected /\ !kDFS /\ kBFS /\ !kCycle /\ kConnectedComps /\
kPrim

(b) Task example for comparing facts from two different variants.

Figure 6. Examples of study task.

###  3.1. Task Design

The study’s tasks fall into three categories: identify facts belonging to a
single product variant, compare facts from two different variants, and compare
facts from three different variants. These tasks are applied to graphical
models of a variability-aware analysis. Figure 5 shows a graphical model of
the results from a variability-aware control-flow analysis starting from the
GPL function execComnd.

Each study question provides a graphical model of variability-aware analysis
results including PC annotations, the task to be performed, and the variants
of interest for that task. Thus, a task to identify facts in a single variant
asks the participant to find instances of function calls or variable
assignments that exist in the given variant. Such tasks simulate how an
engineer might investigate control- and data-flows among functions or
variables. Figure 6(a) shows an example of this kind of task. A task to
compare the facts between two different variants specifies two variants of
interest and asks the subject to find specific facts in the intersection,
union, or set-difference of the two variants (Figure 6(b)). The set-difference
of variants could represent the enabling or disabling of a single feature,
simulating how an engineer might assess the impact of modifying a feature
configuration. Lastly, a task to compare among multiple variants extends a
comparison task to three variants of interest.

The tasks of the study were divided into two stages. In the first stage, the
participants interacted freely with a Neo4j database and visualizer via a
publicly accessible webpage while sharing their screens with the researcher.
Both the control group and the treatment group performed three tasks on each
of the two models. Both groups had to run Neo4j queries (provided by the
study) to create the tasks’ models, and both groups used their respective
visualizers to customize the models. Treatment participants were able to
create coloured filters that highlight a variant’s facts, whereas control
participants could use only Neo4j’s basic customization options.

In the second stage of the study, the participants answered an online survey
comprising twelve comprehension questions about four models. The models were
screenshots that the participants could not modify; and the four models
provided to the treatment group covered each of the visualization options
(i.e., $ArrowStripes$, $ArrowSegments$, $ArrowShapes$, and $SeparateArrows$).
Different treatment participants experienced the visualization options in
different orders, according to a balanced Latin square design (grant1948latin,
), to decrease any effect the presentation order could have on the
participants’ performance. The control group performed identical tasks on
versions of the models with uncolored edges.

During the study, we discovered that one of the second-stage questions was
phrased ambiguously, which confused some of the participants. Thus data
collected from that particular question were removed from our analyses of the
participants’ performance.

The complete list of study questions and other materials like the screening
questionnaire, pre-study tutorial, the GPL code base, the post-study feedback
form, and study results can be found in an anonymous git
repository222https://github.com/paperMaterial4/icse2024comprehending created
for this paper.

###  3.2. Recruitment

We advertised the study to students in our university’s second- and fourth-
year Computer Science (CS) and Software Engineering (SE) courses. Students in
these courses are expected to be familiar with Boolean logic and configurable
software (e.g., using C preprocessor directives) from previous courses on
logic and software design. In addition, most students at that level will have
completed 1-4 internships at tech companies. To further ensure participants
were proficient in these concepts, all 63 students who expressed interest in
participating in the study completed a screening questionnaire that assessed
their understanding of the graph product line (GPL) and models annotated with
presence conditions. Students who correctly answered at least six of the seven
screening questions were deemed eligible to participate in the study. Forty-
two students were invited to schedule a study session.

Every study session started with a written tutorial that introduced the
participants to the Neo4j Browser (original or variability-aware) and its
customization options. The tutorial included a few demo tasks asking questions
about small models (with 3-4 nodes) and instructing participants to use the
customization options. It took participants about an hour to complete both the
tutorial and the user study. Study participants received $50 in appreciation
for their participation.

###  3.3. Application Domain

The study’s comprehension tasks are performed on the results of variability-
aware queries of the graph product line (GPL) introduced in Section 2. The GPL
was designed to use graph concepts that are familiar to second-year CS and SE
students (thereby mitigating against accidental complexities induced by the
application domain), yet represent a non-trivial SPL (e.g., not all features
are compatible).

###  3.4. Treatment Allocation

We distributed the students into the control and treatment groups by
alternating the inclusion of new participants in each group based on the
initial schedule of study sessions. Whenever a participant had to reschedule,
their allocation persisted to the group to which they were originally
assigned. Alternating allocation was also applied to the distribution of
treatment participants to the four different orderings of the filter
visualization options.

###  3.5. Data Collection and Metrics

In order to test our hypotheses, during the study we collected the
participants’ solutions and times on tasks. Correctness of a participant’s
solution was measured by comparing them to objectively correct answers. A
solution was assessed as either correct or not, with no notion of partial
correctness. Time on task measures the time a participant spent working on a
task before submitting an answer. The mental effort applied to each category
of tasks is self-reported by participants using an online version of
Subjective Mental Effort Questionnaire (SMEQ) scale (sauro2009comparison, ).
The scale has nine labels, ranging from “Not at all hard to do” to
“Tremendously hard to do”, which are distributed over numerical scores ranging
from 0 to 150.

Participants’ self-reported mental effort and opinions of the visualizer were
collected in a post-study feedback form. The form has four parts:

  1. (1)

Easy of Use: Participants were given eight statements about the usability of
the visualizer and asked to provide their level of agreement in terms of a
Likert scale (allen2007likert, ). Control and treatment received group-
specific statements regarding their respective visualizers. For example, the
first statement of the two feedback forms state "I found that interpreting the
[Boolean expressions vs. coloured filters] were unnecessarily complex",
respectively. The statements vary as to whether they are positive or negative
about the user experience, to avoid influencing participants’ answers.

  2. (2)

Self-reported mental effort: Participants reported the degree of mental effort
they applied for each task category, using horizontal sliders ranging over the
SMEQ scale (sauro2009comparison, ), as shown in Figure 7.

  3. (3)

Ranked preferences for the visualization features: Ranked preferences were
collected using the $100 prioritization method (leffingwell2000managing, ).
Control participants were asked to distribute a hypothetical $100 dollars to
missing features they would have liked to see in their visualizer tasks;
options included the ability to customize Boolean expressions, to elide edges
that do not apply in a variant, and to colour edges based on the variants to
which they apply. Treatment-group participants did the same $100
prioritization exercise, but they ranked the four visualization options for
highlighting filter results.

  4. (4)

Comments: Two open-ended questions ask participants for comments on their
experiences ("What are your general impressions of the presented tool?) and
for suggested improvements to the visualizer ("Do you have any suggestions for
improvements to the presented tool? If so, please describe them below.").

Figure 7. SMEQ scale used in the user study.

##  4\. Evaluation Results

Of the 42 participants in our study, 38 are undergraduate students, and 4 are
PhD students; 29 of the 42 are men. Two participants declared they have full
or partial red-green colour blindness. Most participants (90%) as majors in
Software Engineering, Computer Science, or Computer Engineering; others are
majors in Statistics, Mechatronics Engineering, or Nanoscience. All
participants passed the screening questionnaire and had either completed or,
at the time of the study, were enrolled in a course that taught configurable
software methodologies (e.g., C preprocessor directives like #ifdef, #ifndef).
Seventeen participants declared they have prior work experience with
configurable software. None had previously used Neo4j.

Three participants in the treatment group chose not to use the coloured
filters in the first stage of the study. We will explore their reasons in the
next sections, but given that this means they didn’t experience the usage of
the treatment visualizer, we removed their stage-one data from our analysis of
participants’ performance.

###  4.1. Efficiency

Our null hypothesis related to efficiency was:

  1. H1

Efficiency: Using the coloured filters does not change the amount of time it
takes to comprehend program variability-aware analysis results.

This hypothesis is rejected ($p<0.01$). The treatment participants finished
all tasks approximately 30% faster than the control participants. We observed
similar time reductions in both stages of the study, suggesting that
participants who used coloured filters took less time to perform study tasks
regardless of whether they had the freedom to customize the model.
Efficiencies observed in the first stage of the study also indicate that the
time that treatment participants took to create and customize filters was
offset by the reduced time it took to interpret the models. Figure 8 shows
summaries of the time the control and treatment groups took during the two
study stages. The box-and-whisker plots on the charts show the distribution of
results. The length of the box represents the interquartile range, the line
through the box shows the median average, the X sign marks the mean average,
and the whiskers indicate the maximum and minimum values observed for that
sample. Data points exceeding $1.5$ times the interquartile range, are
classified as outliers and are represented by dots above or below the boxes.

Figure 8. Average time to perform tasks, disaggregated by study stage.

We see the same efficiency gains regardless in some of the type of task being
performed. The treatment participants were faster in all task categories, but
they were significantly faster when identifying facts belonging to a given
variant and comparing facts from three variants ($p<0.01$). Participants’
average had a reduction of 22% when working with a single variant and 44% when
multiple variants were considered. When comparing results from two variants,
participants’ average time was not significantly different from the control
group ($0.05<p<0.1$). Figure 9 compares the task times for both participant
groups, disaggregated by the task category.

Figure 9. Average time to perform tasks, disaggregated by task category.

###  4.2. Correctness

Our null hypothesis related to correctness was:

  1. H2

Correctness: Using coloured filters does not change the number of mistakes
made when comprehending variability-aware analysis results.

The hypothesis is rejected as the treatment participants made fewer mistakes,
especially in the first stage of the study ($p<0.01$), where participants from
the control group had an average error rate almost six times higher than
participants who used the coloured filters. Figure 10 shows the average
accuracies of participants in both stages of the study.

Looking in greater detail at the errors made, the most common error was
failure to discern the direction of edges (or to notice that edges were
directed), which is required to comprehend directed relationships (e.g.,
calling vs. called functions); 62% of the control participants made such a
mistake on at least one task, whereas 11% of the treatment participants
committed this same error. Control participants were also more likely to
misinterpret the scope of a task when asked for singleton function calls made
by a function of interest, a quarter of the control participants reported
entire call chains starting from that function. None of the participants from
the treatment group made such a mistake. Very few participants from either
study group made mistakes in determining which model elements belong to the
variants of interest.

In stage 2 of the study, the two groups’ accuracy is not statistically
significant ($0.2<p$). Control participants performed better than in the first
stage, and treatment participants performed slightly worse, making mistakes
they did not make in the first stage; in particular, one outlier achieved only
36% correctness in their stage 2 tasks. Recall that the differences between
stage 1 and stage 2 tasks are twofold: (1) In stage one, participants
interacted with the Neo4j tool, entering queries, possibly customizing the
visualization of the query result, and answering variant-specific questions
about the query results; whereas in stage 2, participants were given images of
query results. (2) In stage two, the models provided to the control group all
exhibit the same view of variable query results (PC annotation on model
elements), whereas the models provided to the treatment group exhibited
different options for highlighting variant-specific results. In Section 6, we
discuss how these differences between the first and second stages of the study
may have affected participants’ performance. Despite the results from stage
two of the study, we reject the null hypothesis based on the results from
stage one, which was a more realistic assessment of participants’ interactions
with the study’s visualizers.

Figure 10. Average participant correctness, disaggregated by study stage.

Comparing the groups’ accuracy disaggregating by task category (shown in
Figure 11), we observed no significant difference in the groups’ accuracy in
any task category.

Figure 11. Average participant correctness, disaggregated by task category.

###  4.3. Cognitive Load

Our null hypothesis related to cognitive load was:

  1. H3

Cognitive load: Using coloured filters does not change the cognitive load of
performing comprehension tasks involving variability-aware analysis results.

This hypothesis is partially rejected, because the results are significant for
tasks comparing two or more variants ($p<0.01$) but not as significant for
tasks identifying results in a single variant ($0.05<p<0.1$). Figure 12 shows
the average cognitive loads reported by the participants, disaggregated by
task category. Treatment participants indicated that identifying results
belonging to a single variant required more or less “A Little Effort” and
control participants indicated such tasks required “Some Effort”, based on the
SMEQ scale. Whereas, the treatment participants reported significantly lower
levels of mental effort (36%) than the control participants when performing
tasks involving two or more variants. The extra effort expended by control
participants is due to their needing to calculate the satisfiability of
variant conditions manually.

One treatment participant classified the mental effort for all task categories
as considerably high. This participant raced through the tutorial on filters,
did not use filters in the first stage of the study (although they were placed
in the treatment group), and among all participants had the worst performance
with respect to accuracy. In the user preferences exercise, they strongly
preferred the uncoloured option for visualizing variants of interest.

Figure 12. Average mental effort expended on tasks, disaggregated by task
category.

###  4.4. User Preferences

Our null hypothesis related to user preference was:

  1. H4

User preference: Users feel indifferent about using coloured filters to
highlight variability-aware analysis results.

This hypothesis is rejected ($p<0.01$). Figure 13 shows the ranked preferences
of visualization features, disaggregated by study group. Both participant
groups expressed strong preferences for having coloured filters. Among control
group participants, 31% ranked “Highlighting links that hold in a program
variant” as their favourite feature for an improved interface. Among the
treatment participants, only 9% favoured uncoloured models. In fact, 71% of
the treatment participants distributed none of their $100 “votes” to the
uncoloured filter options.

(a) Control group’s preferred choices for improvements to visualizer.

(b) Treatment group’s preferred choices for visualizing variant-specific
results.

Figure 13. Participants’ preferred features

###  4.5. Filter Visualization Options

Our null hypothesis on differences between options for visualizing variant-
specific results was:

  1. H5

Filter Visualization Options: The filters visualization options have the same
impact on user efficiency and correctness.

This hypothesis is accepted, as no difference was observed in the treatment
participants’ performance when using the different filter visualization
options (considering a significance level of 1%). Figure 14 compares the time
and correctness of responses achieved by treatment participants using each of
the filter visualization options. Even though more participants correctly
solved all the tasks using the Separate Arrows visualization, the average
correctness for that visualization was not significantly different from the
results achieved with the other options. As Figure 14(b) shows, few
participants made mistakes using the Separate Arrows visualization (4 out of
21). However, one specific outlier solved all tasks incorrectly with that
visualization, which decreased significantly the average correctness for the
Separate Arrows visualization.

(a) Time to complete second-stage tasks, disaggregated by filter visualization
(treatment group only).

(b) Correctness of second stage tasks, disaggregated by filter visualization
(treatment group only).

Figure 14. Correctness and time comparison for filter visualization options.

Table 1 summarizes the results of our study’s null-hypothesis tests, including
results disaggregated by the stage of the study and the task category.
Rejected null hypotheses are highlighted in bold.

###  4.6. Participants’ Feedback

Participants’ responses to the list of statements and the open-ended questions
helped us understand their opinions about the coloured filters. Figure 15
shows the agreement levels of study participants to the presented statements.
The treatment group is more homogeneous in strongly disagreeing that coloured
filters are complex and cumbersome (Q2). When shown the same statement about
Boolean expressions, the control group gave more diverse responses, with more
participants being neutral or slightly agreeing with the statement.

Control participants also acknowledge that they need to expend extra effort
when dealing with Boolean expressions and uncoloured models. More than 50% of
the control participants either agreed or were neutral about saying there was
a significant learning curve before they could identify the program variants
in which particular results hold (Q4). Fewer than a quarter of the treatment
participants agreed with that statement. That said, 85% of the control
participants agreed that Boolean expressions are easy to access (Q5), whereas
71% of the treatment group says the same about the filter customization.

(a) Control group

(b) Treatment group

Figure 15. Level of agreement to experience statements.

Participants’ feedback collected by the open-ended questions highlighted the
strengths and weaknesses of the visualizer. Overall, all participants
considered the visualizer easy to use and intuitive. Some of the participants
acknowledged minor problems they had with the visualizer, such as arrowhead
sizes, text styling, and unclear colour selection. Treatment participants who
chose not to use the filters in the first stage of the study singled out the
difficulty in selecting the colour as the main obstacle to using the filters.
Other improvements suggested by the participants include making the filter
customization easier to use and improving the presentation of Boolean
expressions.

Lastly, participants in both groups raised concerns with the visualization of
large models. In particular, they worried that their presentation would be
cluttered and that textual labels would overlap making them difficult to read.
Although the model layout was not assessed as part of this study, this concern
is worth investigating in the future.

Table 1. Statistical Tests of Hypotheses (rejected hypotheses in bold).

Hypothesis | Sub-Hypothesis | P-Value
---|---|---
| Stage 1 | $\boldsymbol{p<0.01}$
| Stage 2 | $\boldsymbol{p<0.01}$
H1. Efficiency | Identify variants’ facts | $\boldsymbol{p<0.01}$
| Compare two variants’ facts | $0.05<p<0.1$
| Compare three variants’ facts | $\boldsymbol{p<0.01}$
| Stage 1 | $\boldsymbol{p<0.01}$
| Stage 2 | $0.2<p$
H2. Correctness | Identify variants’ facts | $0.2<p$
| Compare two variants’ facts | $0.2<p$
| Compare three variants’ facts | $0.2<p$
| Identify variants’ facts | $0.05<p<0.1$
H3. Cognitive Load | Compare two variants’ facts | $\boldsymbol{p<0.01}$
| Compare three variants’ facts | $\boldsymbol{p<0.01}$
H4. User Preference |  | $\boldsymbol{p<0.01}$
H5. Filter Visualization Options | Efficiency | $0.2<p$
Correctness | $0.2<p$

##  5\. Threats to validity

Our user study may present threats to construct validity due to limitations of
the study design and biases introduced by the student participants. We aimed
to partially mitigate those threats by balancing out the study experience and
ascertaining student proficiency with configurable software.

The level of proficiency of participants with respect to the development of
configurable software development and the study design may have threats to
external validity. We mitigated these threats by assessing the eligibility of
participants before study participation and using a rich yet accessible
standard product line (lopez2001standard, ) for the basis of the study.
Moreover, our screening questionnaire helps eliminate the threat that
participants have biases against reasoning about Boolean expressions.

It is important to note that participants’ performances in the study did not
include the time it would take to formulate variants’ presence conditions. In
the study, both the control and the treatment groups were given the PC
expressions that specify the variant(s) of interest for each task. We do not
believe that providing these PC expressions affects the results of the study.
In practice, an engineer would need a sufficiently precise specification of
the variants of interest regardless of whether they are working with the
original Neo4j Browser and are trying to filter analysis results manually or
are working with the treatment visualizer and need to formulate filter
expressions. The study evaluates only whether the treatment visualizer eases
tasks related to reading, comprehending, and reasoning about variability-aware
analysis results - it does not evaluate the user’s experience in formulating
variants’ PCs, which remains a challenging and error-prone task.

An obvious threat to validity is the generalizability of our results to large
SPLs that have more program data and variants. Mitigating this threat is not a
simple challenge, as program data limits on the amount of information that
user study participants are capable of consuming before becoming fatigued. We
partially mitigate the threat by using a manageable but reasonably diverse SPL
as the basis of our user study.

The learning effects of the interface and the unbalanced allocation of
participants could also pose threats to internal validity. To mitigate the
effect of such threats, we present a constant order of tasks to all
participants. For the treatment group, we also varied the order in which the
treatment visualization options were used to generate enough data points to
support statistically valid findings. The allocation of participants was
alternated to ensure that both control and treatment groups had the same
number of participants.

##  6\. Discussion

The results of our study suggest that highlighting variant-specific model
elements enables users to comprehend variability-aware analysis results in
less time and with less mental effort. This result reflects also participants’
descriptions of their experiences. Control participants recognized the
difficulties the tasks (e.g., "…I still need to take quite some effort to
verify the Boolean expression in my head, which is exhaustive."), while some
of the treatment participants highlighted the benefits of having access to the
filters (e.g., "It greatly reduces the mental load by allowing you to abstract
the program variant without considering every parameter."). The treatment
participants completed their tasks more quickly despite the extra work of
creating and customizing filters. The reduced mental effort was especially
evident when tasks compare the analysis results for two or more program
variants. We believe that such gains could further improved if the visualizer
allowed users to choose whether the PC labels on model elements are elided or
exposed.

The impact of coloured filters on task correctness depended on participants’
interactions with the models. When given the option to customize the models,
the participants who used coloured filters performed significantly better than
those who were forced to interpret the model’s Boolean expressions. Two of the
most common errors made by the control group were (1) misreading the direction
of edges (i.e., arrowheads) and (2) reporting paths that originate from a
particular node instead of reporting only the node’s direct neighbours. We
hypothesize that the high mental effort and attention needed to reason about
the model’s presence conditions and customize the model (e.g., move nodes
around, hide edges of a particular type) distracted them from fundamental
details of the model and the task.

When participants did not have the freedom to customize the models, the
coloured filters did not have as significant an impact on the correctness of
the participants’ work. The control participants seem to benefit from being
unable to customize the models. Rather than being subjected to the tool’s
automated layout of models, they were provided readable and uncluttered
models, which lowered the required mental effort and allowed them to produce
more accurate results compared with their performance in the first stage of
the study. Also, the models provided in the second stage had a consistent look
in every task, which might have increased familiarity with the models, leading
to improve performance.

The treatment participants were also given readable and uncluttered models in
the second stage of the study, but different tasks employed different filter
visualizations, and the changing visualizations may have affected their
second-stage performance. The different filter visualization options resulted
in no significant difference in participants’ time or correctness of task
results, but participants had personal preferences. Two options, Separate
Arrows and Arrow Segments, received more than half the participants’ “votes”.
The participants’ feedback suggest that the interface could be improved by
merging the Arrow Shapes and Arrow Segments options (since a solid segment is
a type of shape) and removing the least desired Arrow Stripes option.

The two stages of the study had the unintended effect of assessing in the
first stage participants’ realistic experiences in using the visualizer (i.e.,
its automated layouts of query results and its filter creation interface) and
assessing in the second stage a more idealized experience, where pre-formatted
models were nicely laid out. Thus, participants’ feedback on the provided
“idealized” models reveal more fundamental issues with the two visualizers,
such as cluttered graphs and overlapping labels. For example, one participant
mentioned "Cluttered graphs need manual organization" and another said "Minor
UI issues that bothered me such as text covering some other text and having to
zoom out a lot to see the whole graph". The control participants’ rankings of
desired visualizer features favoured being able to search for terms used in
Boolean expressions and to hide edges that do not hold in a program variant.
The development of such design choices should be the future focus of the
visualizer.

##  7\. Background and Related Works

Our work differs from previous works in its focus on the evaluation of
visualizing variability-aware analysis results and the effectiveness of the
visualization options.

###  7.1. Visualizing Program-Analysis Results

The conventional use of graphical software models is to support the analysis
and understanding of relations between software elements. Such understanding
can facilitate several software processes, such as software evolution
(wilde2018merge, ), software refactoring (beck2011visual, ), and reverse
engineering (storey2001shrimp, ; daniel2014polyptychon, ). More specifically,
lower-level maintenance tasks (sillito2008asking, ) and the reachability
questions (latoza2010developers, ) posed by engineers while performing such
tasks are among the primary goals of interactive graphical software tools.

For example, IDE tools like Zest Sequence Viewer (bennett2007working, ), Graph
Buddy (borowski2022graph, ), Reacher (latoza2011visualizing, ), and ReachHover
(yoo2022investigating, ) enable the exploration and visualization of different
types of connective program data (e.g., control flow traces, dataflow traces,
dependencies, inheritance). The user selects the types of code relations and
elements of interest to initiate an interactive exploration of the program
model. Similarly, JavaRelationshipGraphs (arora2019javarelationshipgraphs, )
extracts a graphical model of a program and uses the Neo4j database and
browser for further analyses of the software, using colour to represent
different types of relations. The comprehension tasks and research questions
in this study are different from those used in previous tool evaluations as
they focus on understanding and reasoning about variability-aware analysis
results.

###  7.2. Visualizing Software Product Lines

Previous works that use colour in SPL visualization do so to distinguish among
features or variability points in the SPL’s source code or feature model.
Tools like CIDE (kastner2009guaranteeing, ), FeatureMapper (Heidenreich-
VISPLE08, ), fmp2rsm (czarnecki2006verifying, ), and FeatureVISU (Apel:2011, )
colourize model or source-code elements according to their association with
the features that the user selects. Such visualization tools contribute to the
engineer’s comprehension and productivity when modifying feature
configurations (asadi2016effects, ).

Other works use coloured models to visualize the results of specific types of
SPL analyses, such as identifying obsolete features (loesch2007optimization,
), consequences of configuration decisions (botterweck2008visual, ), and
feature constraints (martinez2014feature, ). In these cases, the colours
highlight the model elements that pertain to each reported analysis result
rather than highlighting the results that pertain to distinct product
variants. The spatial distribution of the model elements is also explored by
some of those visualizers. However, the cited works do not include observed
experiments with users in their evaluation. They normally evaluate the
correctness of their visualization through a case study. When user feedback is
mentioned, it is unclear whether it is based on users’ actual experience with
the tool.

The evaluations performed by Strüber et al. (struber2020variability, ) and
Shahin et al. (shahin2023applying, ) are closest to our work, but the former
diverges in the scope of the tool, and the latter lacks a proper user study.
In (struber2020variability, ), multiple variability representations are
evaluated in a user study with many participants performing variability
comprehension tasks that are similar to those used in our evaluation. Their
work focuses on the visualization of variable class diagrams, while our work
evaluates the comprehension of variability-aware analysis results. Shahin et
al. (shahin2023applying, ) introduced the coloured filter interface evaluated
in this work. However, their evaluation was limited to users’ impressions and
suggestions based on a demonstration of the tool. Our work evaluates the
interface more thoroughly by measuring and analyzing the impact of the
coloured filters on user understanding.

##  8\. Conclusion

Comprehending SPL analysis results can be particularly challenging for
engineers. On top of the difficulties of parsing and understanding reported
program data, the user is expected to mentally determine whether results hold
in variants of interest. We have evaluated the use of an interactive
visualizer that supports comprehension of variability-aware analysis results
by highlighting those that belong to relevant variants specified by the user.
We learned that the visualizer can provide significant gains in time,
correctness, and cognitive load to users performing a variety of comprehension
tasks. The study’s results also suggest future improvements to the visualizer
including layout algorithms that avoid overlapping model labels, optional
eliding of PC annotations, and simplifications to the filter visualization
options.

## References

  * (1) T. D. LaToza and B. A. Myers, “Developers ask reachability questions,” in _Proceedings of the ACM/IEEE International Conference on Software Engineering (ICSE’10)_ , 2010, pp. 185–194.
  * (2) J. Sillito, G. C. Murphy, and K. De Volder, “Asking and Answering Questions during a Programming Change Task,” _IEEE Transactions on Software Engineering_ , vol. 34, no. 4, pp. 434–451, 2008.
  * (3) M. Barnett, R. DeLine, A. Lal, and S. Qadeer, “Get me here: Using verification tools to answer developer questions,” Technical Report MSR-TR-2014-10, Tech. Rep., 2014.
  * (4) LaToza, Thomas D., “Answering Reachability Questions,” Ph.D. dissertation, Institute for Software Research, Carnegie Mellon University, 2011\.
  * (5) J. Yoo, “Investigating Data-flow Reachability Questions,” Master’s thesis, University of British Columbia, 2022.
  * (6) P. Clements and L. Northrop, _Software Product Lines: Practices and Patterns_. Addison-Wesley Professional, 2001.
  * (7) E. Bodden, T. Tolêdo, M. Ribeiro, C. Brabrand, P. Borba, and M. Mezini, “SPLLIFT: Statically Analyzing Software Product Lines in Minutes Instead of Years,” _ACM SIGPLAN Notices (SIGPLAN’13)_ , vol. 48, no. 6, pp. 355–364, 06 2013.
  * (8) A. Classen, P. Heymans, P.-Y. Schobbens, A. Legay, and J.-F. Raskin, “Model Checking Lots of Systems: Efficient Verification of Temporal Properties in Software Product Lines,” in _Proceedings of the ACM/IEEE International Conference on Software Engineering (ICSE’10)_ , 2010, pp. 335–344.
  * (9) S. Apel, C. Kästner, A. Größlinger, and C. Lengauer, “Type Safety for Feature-Oriented Product Lines,” _Automated Software Engineering_ , vol. 17, no. 3, pp. 251–300, 2010.
  * (10) J. Liebig, A. von Rhein, C. Kästner, S. Apel, J. Dörre, and C. Lengauer, “Scalable Analysis of Variable Software,” in _Proceedings of the Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE’13)_ , 2013, p. 81–91.
  * (11) K. Lauenroth, K. Pohl, and S. Toehning, “Model Checking of Domain Artifacts in Product Line Engineering,” in _Proceedings of the IEEE/ACM International Conference on Automated Software Engineering (ASE’09)_ , 2009, pp. 269–280.
  * (12) R. Shahin, R. Toledo, R. Hackman, J. M. Atlee, and M. Chechik, “Applying Declarative Analysis to Industrial Automotive Software Product Line Models,” _Empirical Software Engineering_ , vol. 28, no. 2, p. 40, 2023\.
  * (13) Neo4j, “Neo4j Graph Database,” accessed July, 2023. [Online]. Available: https://neo4j.com/
  * (14) R. E. Lopez-Herrejon and D. Batory, “A Standard Problem for Evaluating Product-line Methodologies,” in _Proceedings of the International Symposium on Generative and Component-Based Software Engineering (GCSE’01)_ , 2001, pp. 10–24.
  * (15) K. Kang, S. Cohen, J. Hess, W. Novak, and A. Peterson, “Feature-Oriented Domain Analysis (FODA) Feasibility Study,” Software Engineering Institute, Carnegie Mellon University, Tech. Rep. CMU/SEI-90-TR-021, 1990.
  * (16) T. Thüm, S. Apel, C. Kästner, I. Schaefer, and G. Saake, “A Classification and Survey of Analysis Strategies for Software Product Lines,” _ACM Computer Surveys_ , vol. 47, no. 1, pp. 6:1–6:45, Jun. 2014\.
  * (17) R. Shahin, M. Akhundov, and M. Chechik, “Annotative Software Product Line Analysis Using Variability-Aware Datalog,” _IEEE Transactions on Software Engineering_ , vol. 49, no. 3, pp. 1323–1341, 2023.
  * (18) M. Young and M. Pezze, _Software Testing and Analysis: Process, Principles and Techniques_. John Wiley & Sons, Inc., 2005.
  * (19) I. J. Davis and M. W. Godfrey, “From Whence It Came: Detecting Source Code Clones by Analyzing Assembler,” in _Proceedings of the Working Conference on Reverse Engineering (WCRE’10)_ , 2010, pp. 242–246.
  * (20) CPPX, “CPPX - C++ Fact Extractor,” Accessed: April 10, 2023. [Online]. Available: https://www.swag.uwaterloo.ca/cppx/index.html
  * (21) M. Bravenboer and Y. Smaragdakis, “Strictly Declarative Specification of Sophisticated Points-To Analyses,” in _Proceedings of the ACM SIGPLAN Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA ’09)_ , 2009, pp. 243–262.
  * (22) B. J. Muscedere, R. Hackman, D. Anbarnam, J. M. Atlee, I. J. Davis, and M. W. Godfrey, “Detecting Feature-Interaction Symptoms In Automotive Software Using Lightweight Analysis,” in _Proceedings of the IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER’19)_ , 2019, pp. 175–185.
  * (23) “Neo4j browser,” https://neo4j.com/developer/neo4j-browser/, accessed: 2023-08-01.
  * (24) D. A. Grant, “The latin square principle in the design and analysis of psychological experiments.” _Psychological bulletin_ , vol. 45, no. 5, p. 427, 1948.
  * (25) J. Sauro and J. S. Dumas, “Comparison of Three One-question, Post-task Usability Questionnaires,” in _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_ , 2009, pp. 1599–1608.
  * (26) I. E. Allen and C. A. Seaman, “Likert scales and data analyses,” _Quality progress_ , vol. 40, no. 7, pp. 64–65, 2007.
  * (27) D. Leffingwell and D. Widrig, _Managing Software Requirements: A Unified Approach_. Addison-Wesley Professional, 2000.
  * (28) E. Wilde and D. German, “Merge-Tree: Visualizing the Integration of Commits into Linux,” _Journal of Software: Evolution and Process_ , vol. 30, no. 2, p. 25, 2018.
  * (29) M. Beck, J. Trümper, and J. Döllner, “A Visual Analysis and Design Tool for Planning Software Reengineerings,” in _Proceedings of the International Workshop on Visualizing Software for Understanding and Analysis (VISSOFT’11)_ , 2011, pp. 1–8.
  * (30) M.-A. Storey, C. Best, and J. Michand, “Shrimp Views: An Interactive Environment for Exploring Java Programs,” in _Proceedings of the International Workshop on Program Comprehension (IWPC’01)_ , 2001, pp. 111–112.
  * (31) D. T. Daniel, E. Wuchner, K. Sokolov, M. Stal, and P. Liggesmeyer, “Polyptychon: A hierarchically-constrained classified dependencies visualization,” in _Proceedings of the IEEE Working Conference on Software Visualization (VISSOFT’14)_ , 2014, pp. 83–86.
  * (32) C. Bennett, D. Myers, M.-A. Storey, and D. German, “Working with ‘Monster’ Traces: Building a Scalable, Usable, Sequence Viewer,” in _In Proceedings of the International Workshop on Program Comprehension Through Dynamic Analysis (PCODA’07)_ , 2007, pp. 1–5.
  * (33) K. Borowski, B. Balis, and T. Orzechowski, “Graph Buddy—an Interactive Code Dependency Browsing and Visualization Tool,” in _Proceedings of the Working Conference on Software Visualization (VISSOFT’22)_ , 2022, pp. 152–156.
  * (34) T. D. LaToza and B. A. Myers, “Visualizing Call Graphs,” in _Proceedings of the IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC’11)_ , 2011, pp. 117–124.
  * (35) R. Arora and S. Goel, “JavaRelationshipGraphs (JRG) Transforming Java Projects into Graphs using Neo4j Graph Databases,” in _Proceedings of the International Conference on Software Engineering and Information Management (ICSIM’19)_ , 2019, pp. 80–84.
  * (36) C. Kästner, S. Apel, S. Trujillo, M. Kuhlemann, and D. Batory, “Guaranteeing Syntactic Correctness for All Product Line Variants: A Language-Independent Approach,” in _Proceedings of the Interntional Conferfence on Objects, Components, Models and Patterns (TOOLS’09))_ , 2009, pp. 175–194.
  * (37) F. Heidenreich, I. Şavga, and C. Wende, “On Controlled Visualisations in Software Product Line Engineering,” in _Proceedings of the International Workshop on Visualisation of Software Product Line Engineering (ViSPLE@SPLC’08)_ , 2008, pp. 335–341.
  * (38) K. Czarnecki and K. Pietroszek, “Verifying Feature-Based Model Templates against Well-Formedness OCL Constraints,” in _Proceedings of Generative Programming: Concepts and Experiences (GPCE’06)_ , 2006, pp. 211–220.
  * (39) S. Apel and D. Beyer, “Feature Cohesion in Software Product Lines: An Exploratory Study,” in _Proceedings of the ACM/IEEE International Conference on Software Engineering (ICSE’11)_. New York, NY, USA: ACM, 2011, pp. 421–430.
  * (40) M. Asadi, S. Soltani, D. Gašević, and M. Hatala, “The Effects of Visualization and Interaction Techniques on Feature Model Configuration,” _Empirical Software Engineering_ , vol. 21, no. 4, pp. 1706–1743, 2016.
  * (41) F. Loesch and E. Ploedereder, “Optimization of Variability in Software Product Lines,” in _Proceedings of International Conference on Software Product Lines (SPLC’07)_ , 2007, pp. 151–162.
  * (42) G. Botterweck, S. Thiel, D. Nestor, S. bin Abid, and C. Cawley, “Visual Tool Support for Configuring and Understanding Software Product Lines,” in _Proceedings of the International Conference on Software Product Lines (SPLC’08_ , 2008, pp. 77–86.
  * (43) J. Martinez, T. Ziadi, R. Mazo, T. F. Bissyandé, J. Klein, and Y. Le Traon, “Feature Relations Graphs: A Visualisation Paradigm for Feature Constraints in Software Product Lines,” in _Proceedings of the IEEE Working Conference on Software Visualization (VISSOFT’14)_. IEEE, 2014, pp. 50–59.
  * (44) D. Strüber, A. Anjorin, and T. Berger, “Variability Representations in Class Models: An Empirical Assessment,” in _Proceedings of the ACM/IEEE International Conference on Model Driven Engineering Languages and Systems (MODELS’20)_ , 2020, pp. 240–251.


* [1] D. Arnold, R. Falk, R. Winther, Finite element exterior calculus: from hodge theory to numerical stability, Bulletin of the American Mathematical society 47 (2) (2010) 281–354.
  * [2] N. Nigam, D. M. Williams, Conforming finite element function spaces in four dimensions, part I: Foundational principles and the tesseract, Computers & Mathematics with Applications.
  * [3] J. Gopalakrishnan, M. Neumuller, P. S. Vassilevski, The auxiliary space preconditioner for the de Rham complex, SIAM Journal on Numerical Analysis 56 (6) (2018) 3196–3218.
  * [4] F. Fuentes, B. Keith, L. Demkowicz, S. Nagaraj, Orientation embedded high order shape functions for the exact sequence elements of all shapes, Computers & Mathematics with Applications 70 (4) (2015) 353–458.
  * [5] M. Behr, Simplex space–time meshes in finite element simulations, International Journal for Numerical Methods in Fluids 57 (9) (2008) 1421–1434.
  * [6] V. Karyofylli, M. Frings, S. Elgeti, M. Behr, Simplex space-time meshes in two-phase flow simulations, International Journal for Numerical Methods in Fluids 86 (3) (2018) 218–230.
  * [7] V. Karyofylli, L. Wendling, M. Make, N. Hosters, M. Behr, Simplex space-time meshes in thermally coupled two-phase flow simulations of mold filling, Computers & Fluids 192 (2019) 104261.
  * [8] M. von Danwitz, V. Karyofylli, N. Hosters, M. Behr, Simplex space-time meshes in compressible flow simulations, International Journal for Numerical Methods in Fluids 91 (1) (2019) 29–48.
  * [9] M. von Danwitz, P. Antony, F. Key, N. Hosters, M. Behr, Four-dimensional elastically deformed simplex space-time meshes for domains with time-variant topology, International Journal for Numerical Methods in Fluids 93 (12) (2021) 3490–3506.
  * [10] P. Foteinos, N. Chrisochoides, 4d space–time Delaunay meshing for medical images, Engineering with Computers 31 (3) (2015) 499–511.
  * [11] P. C. Caplan, R. Haimes, D. L. Darmofal, M. C. Galbraith, Anisotropic geometry-conforming d-simplicial meshing via isometric embeddings, Procedia Engineering 203 (2017) 141–153.
  * [12] P. Caplan, R. Haimes, D. Darmofal, M. Galbraith, Extension of local cavity operators to 3d+t space-time mesh adaptation, in: AIAA Scitech 2019 Forum, 2019\.
  * [13] P. C. Caplan, Four-dimensional anisotropic mesh adaptation for spacetime numerical simulations, Ph.D. thesis, Massachusetts Institute of Technology (2019).
  * [14] P. C. Caplan, R. Haimes, D. L. Darmofal, Four-dimensional anisotropic mesh adaptation, Computer-Aided Design (2020) 102915.
  * [15] C. V. Frontin, G. S. Walters, F. D. Witherden, C. W. Lee, D. M. Williams, D. L. Darmofal, Foundations of space-time finite element methods: Polytopes, interpolation, and integration, Applied Numerical Mathematics 166 (2021) 92–113.
  * [16] J. T. Anderson, D. M. Williams, A. Corrigan, Surface and hypersurface meshing techniques for space-time finite element methods, Computer-Aided Design (2023) 103574.
  * [17] T. E. Tezduyar, S. Sathe, R. Keedy, K. Stein, Space–time finite element techniques for computation of fluid–structure interactions, Computer Methods in Applied Mechanics and Engineering 195 (17-18) (2006) 2002–2027.
  * [18] T. E. Tezduyar, S. Sathe, Modelling of fluid–structure interactions with the space–time finite elements: Solution techniques, International Journal for Numerical Methods in Fluids 54 (6-8) (2007) 855–900.
  * [19] T. E. Tezduyar, K. Takizawa, C. Moorman, S. Wright, J. Christopher, Space–time finite element computation of complex fluid–structure interactions, International Journal for Numerical Methods in Fluids 64 (10-12) (2010) 1201–1218.
  * [20] T. E. Tezduyar, K. Takizawa, T. Brummer, P. R. Chen, Space–time fluid–structure interaction modeling of patient-specific cerebral aneurysms, International Journal for Numerical Methods in Biomedical Engineering 27 (11) (2011) 1665–1710.
  * [21] K. Takizawa, Y. Bazilevs, T. E. Tezduyar, Space–time and ALE-VMS techniques for patient-specific cardiovascular fluid–structure interaction modeling, Archives of Computational Methods in Engineering 19 (2012) 171–225.
  * [22] T. Kuraishi, K. Takizawa, T. E. Tezduyar, Space–time isogeometric flow analysis with built-in Reynolds-equation limit, Mathematical Models and Methods in Applied Sciences 29 (05) (2019) 871–904.
  * [23] T. Terahara, K. Takizawa, T. E. Tezduyar, Y. Bazilevs, M.-C. Hsu, Heart valve isogeometric sequentially-coupled fsi analysis with the space–time topology change method, Computational Mechanics 65 (2020) 1167–1187.
  * [24] Y. Bazilevs, K. Takizawa, T. E. Tezduyar, M.-C. Hsu, Y. Otoguro, H. Mochizuki, M. C. Wu, ALE and space–time variational multiscale isogeometric analysis of wind turbines and turbomachinery, Parallel Algorithms in Computational Science and Engineering (2020) 195–233.
  * [25] T. E. Tezduyar, K. Takizawa, Space–time computations in practical engineering applications: a summary of the 25-year history, Computational Mechanics 63 (4) (2019) 747–753.
  * [26] D. N. Arnold, R. S. Falk, R. Winther, Finite element exterior calculus, homological techniques, and applications, Acta Numerica 15 (2006) 1–155.
  * [27] D. N. Arnold, Finite element exterior calculus, SIAM, 2018.
  * [28] A. Natale, Structure-preserving finite element methods for fluids, Ph.D. thesis, Imperial College London (2017).
  * [29] A. T. McRae, G.-T. Bercea, L. Mitchell, D. A. Ham, C. J. Cotter, Automated generation and symbolic manipulation of tensor product finite elements, SIAM Journal on Scientific Computing 38 (5) (2016) S25–S47.
  * [30] P. Monk, Finite element methods for Maxwell’s equations, Numerical Mathematics and Scientific Computation, Oxford University Press, New York, 2003.  doi:10.1093/acprof:oso/9780198508885.001.0001.
URL https://doi.org/10.1093/acprof:oso/9780198508885.001.0001

  * [31] D. N. Arnold, Spaces of finite element differential forms, in: U. Gianazza, F. Brezzi, P. Colli Franzone, G. Gilardi (Eds.), Analysis and Numerics of Partial Differential Equations, Springer, 2013, pp. 117–140.  doi:10.1007/978-88-470-2592-9_9.
  * [32] D. N. Arnold, D. Boffi, F. Bonizzoni, Finite element differential forms on curvilinear cubic meshes and their approximation properties, Numerische Mathematik 129 (1) (2015) 1–20.
  * [33] M. S. Petrov, T. D. Todorov, G. S. Walters, D. M. Williams, F. D. Witherden, Enabling four-dimensional conformal hybrid meshing with cubic pyramids, Numerical Algorithms 91 (2) (2022) 671–709.

##  Appendix A Construction of Spaces on the Pentatope

Following the procedure of [26], we begin by defining

$\displaystyle
V_{k}\Lambda^{s}(\mathfrak{T}^{4})=P^{k-1}\Lambda^{s}\oplus\kappa\tilde{P}^{k-1}\Lambda^{s+1},$

where $\kappa$ is the Koszul differential. We will consider the cases of
$s=1,2,3,4$ in what follows. For each case, we will define the Koszul
differential and introduce the associated spaces.

  * 1.

1-forms: associated with vectors in $\mathbb{R}^{4}$

$\displaystyle\omega$
$\displaystyle=a_{1}dx^{1}+a_{2}dx^{2}+a_{3}dx^{3}+a_{4}dx^{4},$
$\displaystyle\Upsilon_{1}\omega$
$\displaystyle:=\left[a_{1},a_{2},a_{3},a_{4}\right]^{T}.$

It follows that $\kappa\omega$ is a 0-form given as

$\displaystyle\kappa\omega$
$\displaystyle=a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}+a_{4}x_{4},$
$\displaystyle\Upsilon_{0}\left(\kappa\omega\right)$ $\displaystyle=a\cdot x.$

  * 2.

2-forms: associated with skew-symmetric matrices in $\mathbb{K}$

$\displaystyle\omega$ $\displaystyle=a_{12}dx^{1}\wedge
dx^{2}+a_{13}dx^{1}\wedge dx^{3}+a_{14}dx^{1}\wedge dx^{4}$
$\displaystyle+a_{23}dx^{2}\wedge dx^{3}+a_{24}dx^{2}\wedge
dx^{4}+a_{34}dx^{3}\wedge dx^{4},$ $\displaystyle\Upsilon_{2}\omega$
$\displaystyle:=\frac{1}{2}\left[\begin{array}[]{cccc}0&a_{12}&a_{13}&a_{14}\\\\[4.30554pt]
-a_{12}&0&a_{23}&a_{24}\\\\[4.30554pt] -a_{13}&-a_{23}&0&a_{34}\\\\[4.30554pt]
-a_{14}&-a_{24}&-a_{34}&0\end{array}\right].$

A Koszul differential on a 2-form is given by

$\displaystyle\kappa dx^{i}\wedge
dx^{j}=x_{i}dx^{j}-dx^{i}x_{j}=x_{i}dx^{j}-x_{j}dx^{i}.$

Therefore, the Koszul differential of $\omega$ (given above) can be expanded
as follows

$\displaystyle\kappa\omega$ $\displaystyle=a_{12}\kappa(dx^{1}\wedge
dx^{2})+a_{13}\kappa(dx^{1}\wedge dx^{3})+a_{14}\kappa(dx^{1}\wedge
dx^{4})+a_{23}\kappa(dx^{2}\wedge dx^{3})$
$\displaystyle+a_{24}\kappa(dx^{2}\wedge dx^{4})+a_{34}\kappa(dx^{3}\wedge
dx^{4})$
$\displaystyle=a_{12}(x_{1}dx^{2}-x_{2}dx^{1})+a_{13}(x_{1}dx^{3}-x_{3}dx^{1})+a_{14}(x_{1}dx^{4}-x_{4}dx^{1})$
$\displaystyle+a_{23}(x_{2}dx^{3}-x_{3}dx^{2})+a_{24}(x_{2}dx^{4}-x_{4}dx^{2})+a_{34}(x_{3}dx^{4}-x_{4}dx^{3})$
$\displaystyle=(-x_{2}a_{12}-x_{3}a_{13}-x_{4}a_{14})dx^{1}+(x_{1}a_{12}-x_{3}a_{23}-x_{4}a_{24})dx^{2}$
$\displaystyle+(x_{1}a_{13}+x_{2}a_{23}-x_{4}a_{34})dx^{3}+(x_{1}a_{14}+x_{2}a_{24}+x_{3}a_{34})dx^{4}$
$\displaystyle\Upsilon_{1}\left(\kappa\omega\right)$
$\displaystyle=\left[\begin{array}[]{cccc}0&a_{12}&a_{13}&a_{14}\\\\[4.30554pt]
-a_{12}&0&a_{23}&a_{24}\\\\[4.30554pt] -a_{13}&-a_{23}&0&a_{34}\\\\[4.30554pt]
-a_{14}&-a_{24}&-a_{34}&0\end{array}\right]\left[\begin{array}[]{c}-x_{1}\\\\[4.30554pt]
-x_{2}\\\\[4.30554pt] -x_{3}\\\\[4.30554pt] -x_{4}\end{array}\right].$

Hence,

$\displaystyle
V_{k}\Lambda^{1}(\mathfrak{T}^{4})=P^{k-1}\Lambda^{1}\oplus\kappa\tilde{P}^{k-1}\Lambda^{2}=(P^{k-1}(\mathfrak{T}^{4}))^{4}\oplus\mathcal{L}((\tilde{P}^{k-1}(\mathfrak{T}^{4}))^{6})x,$

where the latter term describes skew-symmetric matrices of homogeneous degree
$k-1$ multiplying the coordinate vector. This is a strict subset of the set of
4-vectors of degree $k$.

Notice that if we take the dot product of the coordinate vector with our
matrix-vector product

$\displaystyle\left[\begin{array}[]{cccc}0&a_{12}&a_{13}&a_{14}\\\\[4.30554pt]
-a_{12}&0&a_{23}&a_{24}\\\\[4.30554pt] -a_{13}&-a_{23}&0&a_{34}\\\\[4.30554pt]
-a_{14}&-a_{24}&-a_{34}&0\end{array}\right]\left[\begin{array}[]{c}-x_{1}\\\\[4.30554pt]
-x_{2}\\\\[4.30554pt] -x_{3}\\\\[4.30554pt] -x_{4}\end{array}\right],$

we get zero. So another way to write our space is given by

$\displaystyle
V_{k}\Lambda^{1}(\mathfrak{T}^{4})=(P^{k-1}(\mathfrak{T}^{4}))^{4}\oplus\\{p\in(\tilde{P^{k}}(\mathfrak{T}^{4}))^{4}|p\cdot
x=0\\}.$

  * 3.

3-forms: associated with vectors in $\mathbb{R}^{4}$

$\displaystyle\omega$ $\displaystyle=a_{123}dx^{1}\wedge dx^{2}\wedge
dx^{3}+a_{134}dx^{1}\wedge dx^{3}\wedge dx^{4}$
$\displaystyle+a_{234}dx^{2}\wedge dx^{3}\wedge dx^{4}+a_{124}dx^{1}\wedge
dx^{2}\wedge dx^{4},$ $\displaystyle\Upsilon_{3}\omega$
$\displaystyle:=\left[a_{234},-a_{134},a_{124},-a_{123}\right]^{T}.$

A Kozsul differential on a 3-form is

$\kappa(dx^{i}\wedge dx^{j}\wedge dx^{k})=x_{i}dx^{j}\wedge
dx^{k}-x_{j}dx^{i}\wedge dx^{k}+x_{k}dx^{i}\wedge dx^{j}.$

Therefore,

$\displaystyle\kappa\omega$ $\displaystyle=a_{123}\kappa(dx^{1}\wedge
dx^{2}\wedge dx^{3})+a_{134}\kappa(dx^{1}\wedge dx^{3}\wedge dx^{4})$
$\displaystyle+a_{234}\kappa(dx^{2}\wedge dx^{3}\wedge
dx^{4})+a_{124}\kappa(dx^{1}\wedge dx^{2}\wedge dx^{4})$
$\displaystyle=a_{123}(x_{1}dx^{2}\wedge dx^{3}-x_{2}dx^{1}\wedge
dx^{3}+x_{3}dx^{1}\wedge dx^{2})$ $\displaystyle+a_{134}(x_{1}dx^{3}\wedge
dx^{4}-x_{3}dx^{1}\wedge dx^{4}+x_{4}dx^{1}\wedge dx^{3})$
$\displaystyle+a_{124}(x_{1}dx^{2}\wedge dx^{4}-x_{2}dx^{1}\wedge
dx^{4}+x_{4}dx^{1}\wedge dx^{2})$ $\displaystyle+a_{234}(x_{2}dx^{3}\wedge
dx^{4}-x_{3}dx^{2}\wedge dx^{4}+x_{4}dx^{2}\wedge dx^{3})$
$\displaystyle=(x_{3}a_{123}+x_{4}a_{124})dx^{1}\wedge
dx^{2}+(-x_{2}a_{123}+x_{4}a_{134})dx^{1}\wedge dx^{3}$
$\displaystyle+(-x_{3}a_{134}-x_{2}a_{124})dx^{1}\wedge
dx^{4}+(x_{1}a_{123}+x_{4}a_{234})dx^{2}\wedge dx^{3}$
$\displaystyle+(x_{1}a_{124}-x_{3}a_{234})dx^{2}\wedge
dx^{4}+(x_{1}a_{134}+x_{2}a_{234})dx^{3}\wedge dx^{4}$
$\displaystyle\Upsilon_{2}\left(\kappa\omega\right)$
$\displaystyle=\frac{1}{2}\left[\begin{array}[]{cccc}0&(x_{3}a_{123}+x_{4}a_{124})&(-x_{2}a_{123}+x_{4}a_{134})&(-x_{3}a_{134}-x_{2}a_{124})\\\
&0&(x_{1}a_{123}+x_{4}a_{234})&(x_{1}a_{124}-x_{3}a_{234})\\\
&*&0&(x_{1}a_{134}+x_{2}a_{234})\\\ &*&*&0\end{array}\right]$
$\displaystyle=\frac{a_{123}}{2}\left[\begin{array}[]{cccc}0&x_{3}&-x_{2}&0\\\
-x_{3}&0&x_{1}&0\\\ x_{2}&-x_{1}&0&0\\\
0&0&0&0\end{array}\right]+\frac{a_{134}}{2}\left[\begin{array}[]{cccc}0&0&x_{4}&-x_{3}\\\
0&0&0&0\\\ -x_{4}&0&0&x_{1}\\\ x_{3}&0&-x_{1}&0\end{array}\right]$
$\displaystyle+\frac{a_{124}}{2}\left[\begin{array}[]{cccc}0&x_{4}&0&-x_{2}\\\
-x_{4}&0&0&x_{1}\\\ 0&0&0&0\\\
x_{2}&-x_{1}&0&0\end{array}\right]+\frac{a_{234}}{2}\left[\begin{array}[]{cccc}0&0&0&0\\\
0&0&x_{4}&-x_{3}\\\ 0&-x_{4}&0&x_{2}\\\ 0&x_{3}&-x_{2}&0\end{array}\right]$
$\displaystyle:=\frac{1}{2}\left(-a_{123}B_{4}-a_{134}B_{2}+a_{124}B_{3}+a_{234}B_{1}\right).$

Hence,

$\displaystyle V_{k}\Lambda^{2}(\mathfrak{T}^{4})$
$\displaystyle=P^{k-1}\Lambda^{2}\oplus\kappa\tilde{P}^{k-1}\Lambda^{3}$
$\displaystyle=\mathcal{L}((P^{k-1}(\mathfrak{T}^{4}))^{6})\oplus\mathrm{span}\left\\{\tilde{P}^{k-1}(\mathfrak{T}^{4})B_{1}+\tilde{P}^{k-1}(\mathfrak{T}^{4})B_{2}+\tilde{P}^{k-1}(\mathfrak{T}^{4})B_{3}+\tilde{P}^{k-1}(\mathfrak{T}^{4})B_{4}\right\\}.$

It turns out that the space of skew-symmetric matrices of homogeneous degree
$k-1$ above has a nice characterization. Each of the matrices $B_{i}$ looks
like a rotation in a coordinate hyperplane. Also, each $B_{i}x=0$. Therefore,
we can write

$\displaystyle
V_{k}\Lambda^{2}(\mathfrak{T}^{4})=\mathcal{L}((P^{k-1}(\mathfrak{T}^{4}))^{6})\oplus\left\\{B\in\mathcal{L}((\tilde{P}^{k}(\mathfrak{T}^{4}))^{6})|Bx=0\right\\}.$

It is worth computing the dimension of

$\displaystyle\mathcal{S}_{k}=\mathrm{span}\left\\{\tilde{P}^{k-1}(\mathfrak{T}^{4})B_{1}+\tilde{P}^{k-1}(\mathfrak{T}^{4})B_{2}+\tilde{P}^{k-1}(\mathfrak{T}^{4})B_{3}+\tilde{P}^{k-1}(\mathfrak{T}^{4})B_{4}\right\\}.$

We first write

$\displaystyle B_{1}=\mathcal{L}\left(\begin{bmatrix}0\\\ 0\\\ 0\\\ x_{4}\\\
-x_{3}\\\
x_{2}\end{bmatrix}\right),\;B_{2}=\mathcal{L}\left(\begin{bmatrix}0\\\
-x_{4}\\\ x_{3}\\\ 0\\\ 0\\\
-x_{1}\end{bmatrix}\right),\;B_{3}=\mathcal{L}\left(\begin{bmatrix}x_{4}\\\
0\\\ -x_{2}\\\ 0\\\ x_{1}\\\
0\end{bmatrix}\right),\;B_{4}=\mathcal{L}\left(\begin{bmatrix}-x_{3}\\\
x_{2}\\\ 0\\\ -x_{1}\\\ 0\\\ 0\end{bmatrix}\right).$

Any particular element $q\in\mathcal{S}_{k}$ can therefore be written as

$q=p_{1}\mathcal{L}\left(\begin{bmatrix}0\\\ 0\\\ 0\\\ x_{4}\\\ -x_{3}\\\
x_{2}\end{bmatrix}\right)+p_{2}\mathcal{L}\left(\begin{bmatrix}0\\\ -x_{4}\\\
x_{3}\\\ 0\\\ 0\\\
-x_{1}\end{bmatrix}\right)+p_{3}\mathcal{L}\left(\begin{bmatrix}x_{4}\\\ 0\\\
-x_{2}\\\ 0\\\ x_{1}\\\
0\end{bmatrix}\right)+p_{4}\mathcal{L}\left(\begin{bmatrix}-x_{3}\\\ x_{2}\\\
0\\\ -x_{1}\\\ 0\\\ 0\end{bmatrix}\right),$ (A.1)

where $p_{1},p_{2},p_{3}$, and $p_{4}$ are each homogeneous polynomials in
$\tilde{P}^{k-1}(\mathfrak{T}^{4})$. The dimension of $\mathcal{S}_{k}$ can
then be computed by examining the rank of the matrix

$\displaystyle C=C(x):=\begin{bmatrix}0&0&x_{4}&-x_{3}\\\ 0&-x_{4}&0&x_{2}\\\
0&x_{3}&-x_{2}&0\\\ x_{4}&0&0&-x_{1}\\\ -x_{3}&0&x_{1}&0\\\
x_{2}&-x_{1}&0&0\end{bmatrix}.$

The matrix $C$ has rank 3 and nullity 1. We can now examine the kernel.
Suppose
$[p_{1},p_{2},p_{3},p_{4}]^{T}\in(\tilde{P}^{k-1}(\mathfrak{T}^{4}))^{4},$ and
$C[p_{1},p_{2},p_{3},p_{4}]^{T}=0$. By inspection, we see that

$\displaystyle x_{4}p_{3}-x_{3}p_{4}=0,\quad-x_{4}p_{2}+x_{2}p_{4}=0,\quad
x_{4}p_{1}-x_{1}p_{4}=0,$ $\displaystyle\Rightarrow
p_{1}=\frac{x_{1}}{x_{4}}p_{4},\quad p_{2}=\frac{x_{2}}{x_{4}}p_{4},\quad
p_{3}=\frac{x_{3}}{x_{4}}p_{4}.$

Therefore, $p_{4}$ must be divisible by $x_{4}$. Now, the set of homogeneous
polynomials in $(x_{1},x_{2},x_{3},x_{4})$ which are divisible by $x_{4}$ have
a dimension given by
$\mathrm{dim}(\tilde{P}^{k-1}(\mathfrak{T}^{4}))-\mathrm{dim}(\tilde{P}^{k-1}(\mathfrak{T}^{3}))$.

Therefore, the dimension of the subset of
$(\tilde{P}^{k-1}(\mathfrak{T}^{4}))^{4}$ which is associated with
$\mathcal{S}_{k}$ is precisely

$\displaystyle\mathrm{dim}((\tilde{P}^{k-1}(\mathfrak{T}^{4}))^{4})-\left(\mathrm{dim}(\tilde{P}^{k-1}(\mathfrak{T}^{4}))-\mathrm{dim}(\tilde{P}^{k-1}(\mathfrak{T}^{3}))\right)=\mathrm{dim}((\tilde{P}^{k-1}(\mathfrak{T}^{4}))^{3})+\mathrm{dim}(\tilde{P}^{k-1}(\mathfrak{T}^{3})).$

  * 4.

4-forms: associated with scalar functions in $\mathbb{R}$. The generic 4-form
is

$\displaystyle\omega=a_{1234}dx^{1}\wedge dx^{2}\wedge dx^{3}\wedge dx^{4},$

and the Koszul differential is

$\displaystyle\kappa\omega$ $\displaystyle=\kappa(a_{1234}dx^{1}\wedge
dx^{2}\wedge dx^{3}\wedge dx^{4})$
$\displaystyle=a_{1234}\left(x_{1}dx^{2}\wedge dx^{3}\wedge
dx^{4}-x_{2}dx^{1}\wedge dx^{3}\wedge dx^{4}+x_{3}dx^{1}\wedge dx^{2}\wedge
dx^{4}-x_{4}dx^{1}\wedge dx^{2}\wedge dx^{3}\right),$
$\displaystyle\Upsilon_{3}\left(\kappa\omega\right)$
$\displaystyle=a_{1234}x.$

Therefore,

$\displaystyle
V_{k}\Lambda^{4}(\mathfrak{T}^{4})=P^{k-1}\Lambda^{3}\oplus\kappa\tilde{P}^{k-1}\Lambda^{4}=(P^{k-1}(\mathfrak{T}^{4}))^{4}\oplus\tilde{P}^{k-1}(\mathfrak{T}^{4})x.$

##  Appendix B Construction of Spaces on the Tetrahedral Prism

In accordance with the notation in Eq. (5.1), the $U$ terms are given by

$\displaystyle U_{0}$ $\displaystyle:=P^{k}\left(\mathfrak{T}^{3}\right),$
$\displaystyle U_{1}$
$\displaystyle:=\Big{\\{}p=p_{1}dx^{1}+p_{2}dx^{2}+p_{3}dx^{3}=\tilde{P}^{k}\left(\mathfrak{T}^{3}\right)dx^{1}+\tilde{P}^{k}\left(\mathfrak{T}^{3}\right)dx^{2}+\tilde{P}^{k}\left(\mathfrak{T}^{3}\right)dx^{3},$
$\displaystyle
x=x_{1}dx^{1}+x_{2}dx^{2}+x_{3}dx^{3}\Big{|}\left(p,x\right)=0\Big{\\}}$
$\displaystyle\oplus
P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{1}+P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{2}+P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{3},$
$\displaystyle U_{2}$
$\displaystyle:=P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{1}+P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{2}+P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{3}\oplus\tilde{P}^{k-1}\left(\mathfrak{T}^{3}\right)\left(x_{1}dx^{1}+x_{2}dx^{2}+x_{3}dx^{3}\right),$
$\displaystyle=P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{2}\wedge
dx^{3}+P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{1}\wedge
dx^{3}+P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{1}\wedge dx^{2}$
$\displaystyle\oplus\tilde{P}^{k-1}\left(\mathfrak{T}^{3}\right)\left(x_{1}dx^{2}\wedge
dx^{3}-x_{2}dx^{1}\wedge dx^{3}+x_{3}dx^{1}\wedge dx^{2}\right),$
$\displaystyle U_{3}$
$\displaystyle:=P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{1}\wedge dx^{2}\wedge
dx^{3},$

and the $W$ terms are given by

$\displaystyle W_{0}$ $\displaystyle:=P^{k}\left(\mathfrak{T}^{1}\right),$
$\displaystyle W_{1}$
$\displaystyle:=P^{k-1}\left(\mathfrak{T}^{1}\right)dx^{4}.$

We note that the two formulations of $U_{2}$ (above) are related to one
another via the Hodge star operator $\star$. With these definitions in mind,
we can now construct the following tensor-product spaces

$\displaystyle\left(U\times W\right)_{0}=$ $\displaystyle
P^{k}\left(\mathfrak{T}^{1}\right)\times P^{k}\left(\mathfrak{T}^{3}\right),$
$\displaystyle\left(U\times W\right)_{1}=$ $\displaystyle
P^{k}\left(\mathfrak{T}^{1}\right)\times\Bigg{(}\Big{\\{}p=p_{1}dx^{1}+p_{2}dx^{2}+p_{3}dx^{3}=\tilde{P}^{k}\left(\mathfrak{T}^{3}\right)dx^{1}+\tilde{P}^{k}\left(\mathfrak{T}^{3}\right)dx^{2}+\tilde{P}^{k}\left(\mathfrak{T}^{3}\right)dx^{3}\Big{|}$
$\displaystyle\qquad\qquad
x=x_{1}dx^{1}+x_{2}dx^{2}+x_{3}dx^{3}+x_{4}dx^{4},\left(p,x\right)=0\Big{\\}}$
$\displaystyle\qquad\qquad\oplus\left(P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{1}+P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{2}+P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{3}\right)\Bigg{)}$
$\displaystyle\oplus P^{k-1}\left(\mathfrak{T}^{1}\right)\times
P^{k}\left(\mathfrak{T}^{3}\right)dx^{4},$ $\displaystyle\left(U\times
W\right)_{2}=$ $\displaystyle
P^{k-1}\left(\mathfrak{T}^{1}\right)\times\Bigg{(}\Big{\\{}p_{1}dx^{1}\wedge
dx^{4}+p_{2}dx^{2}\wedge dx^{4}+p_{3}dx^{3}\wedge dx^{4},$
$\displaystyle\qquad\qquad\quad=\tilde{P}^{k}\left(\mathfrak{T}^{3}\right)dx^{1}\wedge
dx^{4}+\tilde{P}^{k}\left(\mathfrak{T}^{3}\right)dx^{2}\wedge
dx^{4}+\tilde{P}^{k}\left(\mathfrak{T}^{3}\right)dx^{3}\wedge dx^{4}\Big{|}$
$\displaystyle\qquad\qquad\quad
x=x_{1}dx^{1}+x_{2}dx^{2}+x_{3}dx^{3}+x_{4}dx^{4},\left(p,x\right)=0\Big{\\}}$
$\displaystyle\qquad\qquad\quad\oplus\left(P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{1}\wedge
dx^{4}+P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{2}\wedge
dx^{4}+P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{3}\wedge dx^{4}\right)\Bigg{)}$
$\displaystyle\oplus
P^{k}\left(\mathfrak{T}^{1}\right)\times\Bigg{(}\left(P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{2}\wedge
dx^{3}+P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{1}\wedge
dx^{3}+P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{1}\wedge dx^{2}\right)$
$\displaystyle\qquad\qquad\oplus\tilde{P}^{k-1}\left(\mathfrak{T}^{3}\right)\left(x_{1}dx^{2}\wedge
dx^{3}-x_{2}dx^{1}\wedge dx^{3}+x_{3}dx^{1}\wedge dx^{2}\right)\Bigg{)},$
$\displaystyle\left(U\times W\right)_{3}=$ $\displaystyle
P^{k}\left(\mathfrak{T}^{1}\right)\times
P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{1}\wedge dx^{2}\wedge dx^{3}$
$\displaystyle\oplus
P^{k-1}\left(\mathfrak{T}^{1}\right)\times\Bigg{(}\Big{(}P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{2}\wedge
dx^{3}\wedge dx^{4}+P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{1}\wedge
dx^{3}\wedge dx^{4}$
$\displaystyle\qquad\qquad\quad+P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{1}\wedge
dx^{2}\wedge dx^{4}\Big{)}$
$\displaystyle\qquad\qquad\quad\oplus\tilde{P}^{k-1}\left(\mathfrak{T}^{3}\right)\Big{(}x_{1}dx^{2}\wedge
dx^{3}\wedge dx^{4}-x_{2}dx^{1}\wedge dx^{3}\wedge dx^{4}+x_{3}dx^{1}\wedge
dx^{2}\wedge dx^{4}\Big{)}\Bigg{)},$ $\displaystyle\left(U\times
W\right)_{4}=$ $\displaystyle P^{k-1}\left(\mathfrak{T}^{1}\right)\times
P^{k-1}\left(\mathfrak{T}^{3}\right)dx^{1}\wedge dx^{2}\wedge dx^{3}\wedge
dx^{4}.$