Variants of the Kaczmarz algorithm for solving linear systems.
Project description
Kaczmarz Algorithms
Variants of the Kaczmarz algorithm for solving linear systems in Python.
Installation
To install Kaczmarz Algorithms, run this command in your terminal:
$ pip install -U kaczmarz-algorithms
This is the preferred method to install Kaczmarz Algorithms, as it will always install the most recent stable release.
If you don't have pip installed, these installation instructions can guide you through the process.
Usage
First, import the kaczmarz
and numpy
packages.
>>> import kaczmarz
>>> import numpy as np
Solving a system of equations
To solve the system of equations 3 * x0 + x1 = 9
and x0 + 2 * x1 = 8
using the Kaczmarz algorithm with the cyclic selection rule, use the kaczmarz.Cyclic.solve
function.
>>> A = np.array([[3, 1],
... [1, 2]])
>>> b = np.array([9, 8])
>>> x = kaczmarz.Cyclic.solve(A, b)
>>> x
array([2., 3.])
Check that the solution is correct:
>>> np.allclose(A @ x, b)
True
Inspecting the Kaczmarz iterates
To access the iterates of the Kaczmarz algorithm with the cyclic selection rule, use the kaczmarz.Cyclic.iterates
function.
>>> A = np.array([[1, 0, 0],
... [0, 1, 0],
... [0, 0, 1]])
>>> b = np.array([1, 1, 1])
>>> x0 = np.array([0, 0, 0]) # Initial iterate
>>> for xk in kaczmarz.Cyclic.iterates(A, b, x0):
... xk
array([0., 0., 0.])
array([1., 0., 0.])
array([1., 1., 0.])
array([1., 1., 1.])
Inspecting the rows/equations used
To access the row index used at each iteration of the Kaczmarz algorithm with the cyclic selection rule, use the ik
attribute of the kaczmarz.Cyclic.iterates
iterable.
>>> iterates = kaczmarz.Cyclic.iterates(A, b, x0)
>>> for xk in iterates:
... print("After projecting onto equation {}: {}".format(iterates.ik, xk))
After projecting onto equation -1: [0. 0. 0.]
After projecting onto equation 0: [1. 0. 0.]
After projecting onto equation 1: [1. 1. 0.]
After projecting onto equation 2: [1. 1. 1.]
The initial value of iterates.ik
is -1
, since no projections have been performed yet at the start of the algorithm.
Creating your own selection strategy
To implement a selection strategy of your own, inherit from kaczmarz.Base
and implement the select_row_index
function.
For example, to implement a strategy which uses of the equations of your system in reverse cyclic order:
>>> class ReverseCyclic(kaczmarz.Base):
... def __init__(self, A, *args, **kwargs):
... super().__init__(A, *args, **kwargs)
... self.n_rows = A.shape[0]
... self.row_index = None
...
... def select_row_index(self, xk):
... if self.row_index is None:
... self.row_index = self.n_rows
... self.row_index = (self.row_index - 1) % self.n_rows
... return self.row_index
Your new class will inherit solve
and iterates
class methods which work the same way as kaczmarz.Cyclic.solve
and kaczmarz.Cyclic.iterates
described above.
>>> iterates = ReverseCyclic.iterates(A, b, x0)
>>> for xk in iterates:
... print("After projecting onto equation {}: {}".format(iterates.ik, xk))
After projecting onto equation -1: [0. 0. 0.]
After projecting onto equation 2: [0. 0. 1.]
After projecting onto equation 1: [0. 1. 1.]
After projecting onto equation 0: [1. 1. 1.]
For information about the optional arguments of solve
and iterates
, as well as the other selection strategies available other than Cyclic
, see readthedocs.io.
Citing
If you use our code in an academic setting, please consider citing our code. You can find the appropriate DOI for whichever version you are using on zenodo.org.
Development
See CONTRIBUTING.md for information related to developing the code.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for kaczmarz-algorithms-0.3.0.tar.gz
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4c851ab763f95d66e1ce99184f11231ad09ec72695befaf6e12c631a0622a312 |
|
MD5 | d50f66c9335fa67a3a6270feeec4ba5f |
|
BLAKE2b-256 | f14f59c1712c6123d57f69cade073d8311b5439a977c50a3e16cb8e8f241cb9b |
Hashes for kaczmarz_algorithms-0.3.0-py2.py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6e3e00e1ffce1e242a36555080656c097e1e11c318c37f7efd7dab8ebf886562 |
|
MD5 | 6237483bd83b7a499b6d5c5f0066b3a6 |
|
BLAKE2b-256 | 8afd58007f3fa1b7a8049a9d2a98adf50a19437332c1130a45d44f381f515ec5 |