Matrix inversion is a mathematical operation that is vital for many use-cases: numerical optimization, solving systems of equations, learning regression models, principal-component analysis. In this bounty we would like you to implement an algorithm for inverting encrypted matrices using Concrete-Python.
Description
Many algorithms exist for matrix inversion but they require modification when applied to FHE. For example, you will need to handle convergence criteria which are not directly translatable to FHE circuits but also to introduce quantization in the inversion algorithm.
Implementation guide
We expect the algorithm to produce results with a high level of correctness for matrices that have a realistic dynamic range (i.e. the values in the matrix have similar range and can be quantized to 8-10 bits). Solutions that do not produce sufficient correctness will be rejected. The rankings of the bounty submissions will be based on the speed of the solutions and we recommend that you use tensorized TLUs (applying TLUs on tensors instead of single scalars) as much as possible.
Your main goal is to minimize errors and make running as performant as possible. Here are a few tips that might be useful:
You should implement invert_matrix function.
You are free to change the function signature to include additional information (e.g., quantization parameters)
If you do that, don't forget to change compilation from fhe.Compiler(invert_matrix, {"x": "encrypted"}) to fhe.Compiler(lambda x: invert_matrix(x, additional, arguments, ...), {"x": "encrypted"})
You are also free to change any other function signature and implementation (e.g., add more parameters to init such as quantization bit-width target)
print(f"Average Error: {np.mean(error):.6f}")
print(f" Max Error: {np.max(error):.6f}")
print(f" Min Error: {np.min(error):.6f}")
print(f" Total Error: {np.sum(error):.6f}")
print()
## Reward
- 🥇 1st place: €10,000
- 🥈 2nd place: €3,500
- 🥉 3rd place: €1,500
_Rewards are attributed based on speed performance on the Amazon EC2 M6i instances._
## Related links and references
- [Concrete documentation](https://docs.zama.ai/concrete)
## Submission
Apply directly to this bounty by opening an application [here](https://github.com/zama-ai/bounty-program/issues/new?assignees=zaccherinij%2C+aquint-zama&labels=%F0%9F%91%8A+User+application&projects=&template=zama-bounty-program--application.md&title=Encrypted%20Matrix%20Inversion).
## Questions?
Do you have a specific question about this bounty? Join the live conversation on the FHE.org discord server [here](https://discord.fhe.org). You can also send us an email at: bounty@zama.ai
Winners
🥇 1st place: A submission by Lcressot
Overview
Matrix inversion is a mathematical operation that is vital for many use-cases: numerical optimization, solving systems of equations, learning regression models, principal-component analysis. In this bounty we would like you to implement an algorithm for inverting encrypted matrices using Concrete-Python.
Description
Many algorithms exist for matrix inversion but they require modification when applied to FHE. For example, you will need to handle convergence criteria which are not directly translatable to FHE circuits but also to introduce quantization in the inversion algorithm.
Implementation guide
We expect the algorithm to produce results with a high level of correctness for matrices that have a realistic dynamic range (i.e. the values in the matrix have similar range and can be quantized to 8-10 bits). Solutions that do not produce sufficient correctness will be rejected. The rankings of the bounty submissions will be based on the speed of the solutions and we recommend that you use tensorized TLUs (applying TLUs on tensors instead of single scalars) as much as possible.
Your should start from this template:
Your main goal is to minimize errors and make running as performant as possible. Here are a few tips that might be useful:
invert_matrix
function.fhe.Compiler(invert_matrix, {"x": "encrypted"})
tofhe.Compiler(lambda x: invert_matrix(x, additional, arguments, ...), {"x": "encrypted"})
print(f"Running...") start = time.time() actual_output = encrypted_matrix_inversion.run(sample_input) end = time.time() print(f"(took {end - start:.3f} seconds)")
print()
error = np.abs(expected_output - actual_output)
print(f"Average Error: {np.mean(error):.6f}") print(f" Max Error: {np.max(error):.6f}") print(f" Min Error: {np.min(error):.6f}") print(f" Total Error: {np.sum(error):.6f}")
print()