使用 Groovy、Apache Commons Math、ojAlgo、Nd4j 和 EJML 进行矩阵计算
作者:_Paul King_
发布时间:2022-08-18 下午 01:41
这篇博客探讨了如何使用 Groovy 和各种库进行矩阵计算:Apache Commons Math、ojAlgo、EJML 和 Nd4j(Eclipse Deeplearning4j 的一部分)。我们还将快速了解如何使用孵化中的 Vector API 进行矩阵计算(JEP 338、414、417 和 426)。
斐波那契数列
斐波那契数列起源于几个世纪前的印度,但以 1202 年出版的出版物《计算之书》的意大利作者的名字命名。在那本出版物中,斐波那契提出用这个数列来计算理想化(生物学上不切实际的)兔子种群的增长。他假设将一对新生的兔子放在田野里;每对兔子在一个月大时开始交配,并在第二个月结束时总是产下一对兔子;兔子从不死,而是永远繁殖下去。斐波那契提出了一个难题:一年内会有多少对兔子?这个数列是这样的
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
我们可以用矩阵来解决这个问题。如果我们将矩阵 自乘 n 次,我们得到 。这是一种称为矩阵幂的运算。让我们使用四个最流行和维护的矩阵库来探讨这个问题。
Apache Commons Math
让我们探讨使用 Apache Commons Math 解决这个问题。Apache Commons Math 是一个轻量级、自包含的数学和统计组件库。矩阵是这个库中线性代数部分的一部分,对于这种情况,双精度值的矩阵是相关的。因此,我们将把斐波那契数表示为双精度值。
double[][] data = [[1d, 1d], [1d, 0d]]
def m = MatrixUtils.createRealMatrix(data)
println m * m * m
println m**6
Commons Math 有一个工厂方法,可以从双精度数组创建矩阵。乘法和幂运算的方法名称恰好与 Groovy 中可用于运算符重载的方法(即 `multiply` 和 `power`)一致,因此我们可以使用 Groovy 方便的简写形式。
当我们运行脚本时,输出如下所示
Array2DRowRealMatrix{{3.0,2.0},{2.0,1.0}} Array2DRowRealMatrix{{13.0,8.0},{8.0,5.0}}
我们可以更进一步,打印矩阵中的值,但结果已经足够清楚了。我们看到斐波那契数列中的值出现在输出中。
EJML
EJML(高效 Java 矩阵库)是一个用于操作实数、复数、稠密和稀疏矩阵的线性代数库。它也是一个 100% 的 Java 解决方案。它具有一些新颖的功能,包括从 Matlab 导入和对半环(GraphBLAS)的支持,半环可用于图算法,其中可以使用稀疏矩阵将图表示为邻接矩阵或关联矩阵。
我们可以使用 EJML 进行相同的计算
def m = new SimpleMatrix([[1d, 1d], [1d, 0d]] as double[][])
def ans = m.mult(m).mult(m)
println ans
6.times { ans = ans.mult(m) }
println ans
乘法方法的名称与可以使用自动运算符重载简写的名称不同,因此我们只调用 EJML 提供的方法。请参阅稍后的语言可扩展性部分,了解我们如何才能添加对与 Commons Math 相同的简写的支持。
EJML 没有幂运算方法,但我们只需调用所需次数的乘法即可达到相同的效果。请注意,我们增加了第二个矩阵的迭代次数,以显示斐波那契数列中的下一批元素。
运行此脚本会产生以下输出
Type = DDRM , rows = 2 , cols = 2 3.0000E+00 2.0000E+00 2.0000E+00 1.0000E+00 Type = DDRM , rows = 2 , cols = 2 5.5000E+01 3.4000E+01 3.4000E+01 2.1000E+01
第一个矩阵的数字与之前相同,第二个矩阵显示了斐波那契数列中的下几个数字(21、34 和 55)。
Nd4j
Nd4j 为 Java 用户提供了 Python 中可用的功能。它包含 numpy 运算和 tensorflow/pytorch 运算的混合。Nd4l 利用原生后端,使其能够在不同的平台上工作,并在扩展时提供高效的运算。
我们斐波那契解决方案的代码与 EJML 非常相似
def m = Nd4j.create([[1, 1], [1, 0]] as int[][])
def ans = m.mmul(m).mmul(m)
println ans
9.times { ans = ans.mmul(m) }
println ans
与前两个库不同的是,Nd4j 支持_整数_矩阵(以及双精度和其他许多数值和相关类型)。
运行脚本会产生以下输出
...
[main] INFO org.nd4j.linalg.factory.Nd4jBackend - Loaded [CpuBackend] backend
...
[main] INFO org.nd4j.linalg.cpu.nativecpu.CpuNDArrayFactory - Binary level Generic x86 optimization level AVX/AVX2
[main] INFO org.nd4j.linalg.api.ops.executioner.DefaultOpExecutioner - Blas vendor: [OPENBLAS]
...
[[ 3, 2],
[ 2, 1]]
[[ 233, 144],
[ 144, 89]]
同样,第一个矩阵与我们之前看到的一样,第二个矩阵沿着斐波那契数列增加了三个元素。
ojAlgo
我们要看的下一个库是 ojAlgo(oj! Algorithms)。它是一个开源的全 Java 数学、线性代数和优化库,支持数据科学、机器学习和科学计算。它声称是目前最快的纯 Java 线性代数库,项目网站上提供了许多支持这一说法的基准测试链接。
以下是我们斐波那契示例的代码
def factory = Primitive64Matrix.FACTORY
def m = factory.rows([[1d, 1d], [1d, 0d]] as double[][])
println m * m * m
println m**15
我们可以看到它支持与 Commons Math 相同的运算符重载功能。
当我们运行脚本时,它会产生以下输出
org.ojalgo.matrix.Primitive64Matrix < 2 x 2 > { { 3.0, 2.0 }, { 2.0, 1.0 } } org.ojalgo.matrix.Primitive64Matrix < 2 x 2 > { { 987.0, 610.0 }, { 610.0, 377.0 } }
正如预期的那样,第一个矩阵与我们之前看到的一样,而第二个矩阵显示了数列中的下三个数字。
探索 Vector API 和 EJML
从 JDK16 开始,Vector API 的各个版本(JEP 338、414、417、426)已作为孵化预览功能提供。HotSpot 编译器之前已经进行了一些最小的优化,可以利用向量硬件指令,但 Vector API 大大扩展了可能的优化范围。我们可以考虑编写自己的代码来利用 Vector API,并可能自己执行矩阵乘法。但是,其中一个库已经这样做了,所以我们将探索这条路径。
EJML 库的主要贡献者已经发布了一个 repo,用于非常早期的原型设计和基准测试。我们将使用其中一个类的
对于我们的小计算,Vector API 提供的优化预计不会很大。但是,我们将对为所有库生成矩阵的第一步进行计算,并且我们将对三个方法(`mult_ikj_simple`、`mult_ikj` 和 `mult_ikj_vector`)中的每一个方法进行 1000 次迭代的循环计算。代码如下所示
def m = new SimpleMatrix([[1, 1], [1, 0]] as double[][])
double[] expected = [3, 2, 2, 1]
def step1, result
long t0 = System.nanoTime()
1000.times {
step1 = new SimpleMatrix(2, 2)
result = new SimpleMatrix(2, 2)
MatrixMultiplication.mult_ikj_simple(m.matrix, m.matrix, step1.matrix)
MatrixMultiplication.mult_ikj_simple(step1.matrix, m.matrix, result.matrix)
assert result.matrix.data == expected
}
long t1 = System.nanoTime()
1000.times {
step1 = new SimpleMatrix(2, 2)
result = new SimpleMatrix(2, 2)
MatrixMultiplication.mult_ikj(m.matrix, m.matrix, step1.matrix)
MatrixMultiplication.mult_ikj(step1.matrix, m.matrix, result.matrix)
assert result.matrix.data == expected
}
long t2 = System.nanoTime()
1000.times {
step1 = new SimpleMatrix(2, 2)
result = new SimpleMatrix(2, 2)
MatrixMultiplication.mult_ikj_vector(m.matrix, m.matrix, step1.matrix)
MatrixMultiplication.mult_ikj_vector(step1.matrix, m.matrix, result.matrix)
assert result.matrix.data == expected
}
long t3 = System.nanoTime()
printf "Simple: %6.2f ms\n", (t1 - t0)/1000_000
printf "Optimized: %6.2f ms\n", (t2 - t1)/1000_000
printf "Vector: %6.2f ms\n", (t3 - t2)/1000_000
此示例在 JDK16 上运行,并使用以下 VM 选项:`–enable-preview –add-modules jdk.incubator.vector`。
输出如下所示
WARNING: Using incubator modules: jdk.incubator.vector
Simple: 116.34 ms
Optimized: 34.91 ms
Vector: 21.94 ms
我们可以在这里看到,即使是对于我们微不足道的计算,也有一些改进。当然,对于更大的问题,使用 Vector API 的好处可能是相当大的。
莱斯利矩阵
早些时候,我们将斐波那契数列描述为用于不切实际的兔子种群,因为兔子永远不会死亡并永远繁殖。事实证明,斐波那契矩阵是一种更通用意模型的特例,该模型可以模拟真实的兔子种群(以及其他事物)。这些是 莱斯利矩阵。对于莱斯利矩阵,种群被划分为不同的类别,并且我们跟踪每个类别在特定时期内的出生率和存活率。我们以特殊形式将此信息存储在矩阵中。可以通过莱斯利矩阵的乘法,根据当前时期每个类别的种群数量计算出下一时期的种群数量。
此技术可用于动物种群或人口计算。莱斯利矩阵可以帮助您确定是否有足够的 X 世代、千禧一代和 Z 世代纳税人来支持正在老龄化且即将退休的婴儿潮一代。复杂的动物模型可能会跟踪动物及其捕食者或猎物的种群数量。可以根据此类信息调整存活率和出生率。鉴于只有雌性才能生育,莱斯利模型通常只会根据雌性种群数量进行,而总种群数量则由此推断出来。
我们将根据莱斯利矩阵的此 视频教程 展示一个袋鼠种群的示例。它可以帮助我们确定袋鼠种群是否受到威胁(也许干旱、火灾或洪水影响了它们的觅食栖息地),或者有利条件是否会导致种群过剩。
按照该示例,我们将袋鼠分为 3 个年龄段:0-3 岁、3-6 岁和 6-9 岁。我们将每三年观察一次人口。0-3 岁的袋鼠出生率 (B1) 为 0,因为它们尚未生育。生育力最强的 3-6 岁袋鼠的出生率 (B2) 为 2.3。老年袋鼠 (6-9 岁) 的出生率 (B3) 为 0.4。我们假设没有袋鼠能活过 9 岁。60% (S1) 的幼年袋鼠存活到下一个年龄段。30% (S2) 的中年袋鼠存活到老年。最初,我们每个年龄段都有 400 只袋鼠。
此模型的代码如下所示
double[] init = [400, // 0..<3
400, // 3..<6
400] // 6..9
def p0 = MatrixUtils.createRealVector(init)
println "Initial populations: $p0"
double[][] data = [
[0 , 2.3, 0.4], // B1 B2 B3
[0.6, 0, 0 ], // S1 0 0
[0 , 0.3, 0 ] // 0 S2 0
]
def L = MatrixUtils.createRealMatrix(data)
def p1 = L.operate(p0)
println "Population after 1 round: $p1"
def p2 = L.operate(p1)
println "Population after 2 rounds: $p2"
def L10 = L ** 10
println "Population after 10 rounds: ${L10.operate(p0).toArray()*.round()}"
此代码产生以下输出
Initial populations: {400; 400; 400} Population after 1 round: {1,080; 240; 120} Population after 2 rounds: {600; 648; 72} Population after 10 rounds: [3019, 2558, 365]
在第一轮之后,我们看到很多幼年袋鼠,但老年袋鼠的数量却令人担忧地下降。在第二轮之后,只有老年袋鼠的数量看起来少得令人担忧。然而,由于年轻一代的数量很健康,我们可以看到,在 10 代之后,总人口确实没有处于危险之中。事实上,人口过剩可能会成为一个问题。
使用矩阵进行加密
凯撒密码 是一种早期用于加密消息的技术。它通过将字母表中的字母移动一定数量来替换字母表中的字母,例如,如果移动到前一个字母,“IBM”将变为“HAL”,如果在字母表中向前移动一个字母,“VMS”将变为“WNT”。这种密码可以通过查看字母或模式词的频率分析来破解。
希尔密码 通过将多个字母分解为加密文本中的每个字母来改进凯撒密码。使用矩阵可以一次查看三个或更多符号。通常,N×N 矩阵(密钥)乘以矩阵形式的消息编码。结果是加密文本的矩阵表示形式(编码形式)。我们使用密钥的逆矩阵来解密消息。
我们需要一种方法来将我们的文本消息转换为矩阵并从矩阵转换回来。一种常见的方案是将 A 编码为 1,将 B 编码为 2,依此类推。我们将只使用每个字符的 ASCII 值。我们定义了 `encode` 和 `decode` 方法来做到这一点
double[][] encode(String s) { s.bytes*.intValue().collate(3) as double[][] }
String decode(double[] data) { data*.round() as char[] }
我们将定义一个 2×2 矩阵作为我们的密钥并使用它来加密。我们将找到密钥的逆矩阵并使用它来解密。如果我们愿意,我们可以使用 3×3 密钥来提高安全性,但代价是处理时间更长。
我们的代码如下所示
def message = 'GROOVY'
def m = new SimpleMatrix(encode(message))
println "Original: $message"
def enKey = new SimpleMatrix([[1, 3], [-1, 2]] as double[][])
def encrypted = enKey.mult(m)
println "Encrypted: ${decode(encrypted.matrix.data)}"
def deKey = enKey.invert()
def decrypted = deKey.mult(encrypted)
println "Decrypted: ${decode(decrypted.matrix.data)}"
运行时,它具有以下输出
Original: GROOVY Encrypted: ĴŔŚWZc Decrypted: GROOVY
这比凯撒密码提供了更高的安全性,但是,鉴于当今的计算能力,希尔密码仍然可以通过足够的暴力破解。因此,希尔密码很少单独用于加密,但它们经常与其他技术结合使用以增加扩散性 - 加强其他技术提供的安全性。
形状操作
我们的最后一个示例着眼于几何变换形状。为此,我们将形状的点表示为向量,并使用表示为矩阵的变换来乘以它们。我们只需要担心角,因为我们将使用 Swing 来绘制我们的形状,并且它有一种方法可以通过给出角来绘制多边形。
首先,我们将使用 Groovy 的 `SwingBuilder` 来设置我们的框架
new SwingBuilder().edt {
def frame = frame(title: 'Shapes', size: [420, 440], show: true, defaultCloseOperation: DISPOSE_ON_CLOSE) {
//contentPane.background = Color.WHITE
widget(new CustomPaintComponent())
}
frame.contentPane.background = Color.WHITE
}
我们这里并没有真正使用 SwingBuilder 的很多功能,但如果我们想添加更多功能,SwingBuilder 会使这项任务更容易。
我们实际上将在自定义组件中绘制我们的形状。我们将定义一些颜色常量,一个 `drawPolygon` 方法,给定一个点矩阵,它将这些点绘制为多边形。我们还将定义一个 `vectors` 方法,将点列表(角)转换为向量,以及一个 `transform` 方法,它是用于创建变换矩阵的工厂方法。
这是代码
class CustomPaintComponent extends Component {
static final Color violet = new Color(0x67, 0x27, 0x7A, 127)
static final Color seaGreen = new Color(0x69, 0xCC, 0x67, 127)
static final Color crystalBlue = new Color(0x06, 0x4B, 0x93, 127)
static drawPolygon(Graphics g, List pts, boolean fill) {
def poly = new Polygon().tap {
pts.each {
addPoint(*it.toRawCopy1D()*.round()*.intValue().collect { it + 200 })
}
}
fill ? g.fillPolygon(poly) : g.drawPolygon(poly)
}
static List<Primitive64Matrix> vectors(List<Integer>... pts) {
pts.collect{ factory.column(*it) }
}
static transform(List<Number>... lists) {
factory.rows(lists as double[][])
}
void paint(Graphics g) {
g.drawLine(0, 200, 400, 200)
g.drawLine(200, 0, 200, 400)
g.stroke = new BasicStroke(2)
def triangle = vectors([-85, -150], [-145, -30], [-25, -30])
g.color = seaGreen
drawPolygon(g, triangle, true)
// transform triangle
...
def rectangle = vectors([0, -110], [0, -45], [95, -45], [95, -110])
g.color = crystalBlue
drawPolygon(g, rectangle, true)
// transform rectangle
...
def trapezoid = vectors([50, 50], [70, 100], [100, 100], [120, 50])
g.color = violet
drawPolygon(g, trapezoid, true)
// transform trapezoid
...
}
}
当我们运行这段代码时,我们会看到我们的三个形状
我们现在可以添加我们的变换。我们将有一个逆时针旋转 90 度的变换。另一个将形状放大 25%,另一个将形状缩小 25%。我们可以简单地将变换相乘来组合变换。我们将对三角形进行两次变换。我们将在两种情况下都旋转,但我们会缩小一个并放大另一个。我们只需将每个点乘以变换矩阵即可应用变换。然后,我们将绘制两个变换后的形状作为轮廓而不是填充(以便更容易区分原始版本和变换后的版本)。这是代码
def rot90 = transform([0, 1], [-1, 0])
def bigger = transform([1.25, 0], [0, 1.25])
def smaller = transform([0.75, 0], [0, 0.75])
def triangle_ = triangle.collect{ rot90 * bigger * it }
drawPolygon(g, triangle_, false)
triangle_ = triangle.collect{ rot90 * smaller * it }
drawPolygon(g, triangle_, false)
对于我们的矩形,我们将有一个简单的变换,它在垂直轴上翻转形状。第二个变换在一个变换中结合了多个变化。我们可以将它拆分为更小的变换,然后将它们相乘 - 但这里它们都在一个变换中。我们在水平轴上翻转,然后应用剪切。然后,我们将变换后的形状绘制为轮廓
def flipV = transform([1, 0], [0, -1])
def rectangle_ = rectangle.collect{ flipV * it }
drawPolygon(g, rectangle_, false)
def flipH_shear = transform([-1, 0.5], [0, 1])
rectangle_ = rectangle.collect{ flipH_shear * it }
drawPolygon(g, rectangle_, false)
对于我们的梯形,我们创建一个逆时针旋转 45 度的变换(回想一下 sin 45° = cos 45° = 0.707)。然后我们创建 6 个变换,分别旋转 45、90、135 度等等。我们将每个变换后的形状绘制为轮廓
def rot45 = transform([0.707, 0.707], [-0.707, 0.707])
def trapezoid_
(1..6).each { z ->
trapezoid_ = trapezoid.collect{ rot45 ** z * it }
drawPolygon(g, trapezoid_, false)
}
当我们运行整个示例时,输出如下所示
我们可以在这里看到,矩阵变换为我们提供了强大的方法来操作图像。我们在这里使用了二维图像,但相同的技术也适用于三维形状。
语言和工具的可扩展性
我们之前看到,一些示例可以使用 Groovy 运算符简写语法,而另一些则不能。以下是库中一些常用方法的摘要
Groovy 运算符 |
+ |
- |
* |
** |
Groovy 方法 |
加 |
减 |
乘 |
幂 |
Commons math |
|
|
|
|
EJML |
|
|
|
- |
Nd4j |
|
|
|
- |
ojAlgo |
|
|
|
|
如果库使用与 Groovy 方法相同的名称,则可以使用简写。
Groovy 提供了许多可扩展性功能。我们不会详细介绍所有细节,而是建议读者阅读 Groovy 的历史 论文,其中提供了更多细节。
总之,该论文为 Commons Math 矩阵定义了以下扩展
RealMatrix.metaClass {
plus << { RealMatrix ma -> delegate.add(ma) }
plus << { double d -> delegate.scalarAdd(d) }
multiply { double d -> delegate.scalarMultiply(d) }
bitwiseNegate { -> new LUDecomposition(delegate).solver.inverse }
constructor = { List l -> MatrixUtils.createRealMatrix(l as double[][]) }
}
这修复了上表中的一些方法名称差异。我们现在可以在矩阵和标量加法以及标量乘法中使用运算符简写。我们还可以在求逆时使用 ~(`bitwiseNegate`)运算符。矩阵构造期间对 `double[][]` 的提及现在也不见了。
该论文继续讨论了如何自动添加矩阵库所需的导入并在需要时提供别名。此博客中的代码清单中未显示导入,但在示例代码存储库的清单中显示。无论如何,导入可以像论文中讨论的那样“配置掉”。最终结果是我们的代码可以像这样完整地显示出来
var m = [[1, 1], [1, 0]] as Matrix
m**6
该论文还讨论了工具可扩展性,特别是 GroovyConsole 的可视化方面。它展示了如何定义输出转换,该转换使用 jlatexmath 库渲染任何矩阵结果。因此,他们不会看到 `Array2DRowRealMatrix{{13.0,8.0},{8.0,5.0}}`,而是会看到矩阵的图形再现。因此,在使用 GroovyConsole 时,最终的用户体验如下所示
在 Jupyter 风格的环境中使用时,可能支持其他漂亮的输出样式。
更多信息
-
ojAlgo 网站 和 GitHub 存储库
-
EJML 网站 和 GitHub 存储库
-
Nd4j 文档 和 GitHub 存储库
结论
我们已经使用 Groovy 编程语言以及 Apache Commons Math、ojAlgo、Nd4j 和 EJML 库检查了许多矩阵的简单应用。您应该确信在 JVM 上使用矩阵并不难,并且您有多种选择。我们还简要了解了 Vector API,它看起来像是 JVM 的一个令人兴奋的新增功能(希望很快就会以非预览模式提供)。